Граф - порядок
Cтраница 1
 |
Граф с четырьмя вершинами и пятью ребрами. [1] |
Граф G порядка р состоит из конечного непустого множества V V ( G), содержащего р вершин, и множества X из q неупорядоченных пар различных вершин; при таком определении автоматически исключаются петли ( ребра, соединяющие вершину с ней самой) и кратные ( параллельные) ребра. Вершины ц и у называются при этом смежными; вершина и и ребро х, так же как вершина v и ребро х, называются инцидентными друг другу. Граф с р вершинами и q ребрами называется ( р, q) - epa ( / OM. Однако мы предполагаем дать большую часть определений. [2]
 |
Граф с четырьмя вершинами и пятью ребрами. [3] |
Граф G порядка р состоит из конечного непустого множества V V ( G), содержащего р вершин, и множества X из q неупорядоченных пар различных вершин; при таком определении автоматически исключаются петли ( ребра, соединяющие вершину с ней самой) и кратные ( параллельные) ребра. Пара х и, v вершин, принадлежащая множеству X, называется ребром графа G и говорят, что ребро х соединяет вершины и и и. Вершины и и v называются при этом смежными; вершина и и ребро х, так же как вершина v и ребро х, называются инцидентными друг другу. Однако мы предполагаем дать большую часть определений. [4]
 |
Шесть различных распределений пометок в графе. -. - v. [5] |
В помеченном графе порядка р вершинам приписываются целые числа от 1 дор. [6]
На рис. 15.4.2 приведены три пары графов порядка 4, которые и вершинно, и реберно изоморфны, но реберный изоморфизм не индуцируется никаким вершинным изоморфизмом. [7]
На рис. 15.4.2 приведены три пары графов порядка 4, которые и вершинно, и реберно изоморфны, но реберный изоморфизм не индуцируется никаким вершинным изоморфизмом. Предоставляем читателю проверить, что для графов, порядок которых пе превосходит 4, подобные отображения исчерпываются этими примерами. [8]
Решение пленительной задачи о нахождении числа графов порядка р было впервые опубликовано, по-видимому, в 1927 году. [9]
В задачах этого параграфа спрашивается о числе графов порядка р, являющихся надграфами данного графа Я. При подсчете таких графов может оказаться полезной экстремальная теория графов. Следовательно, для решения соответствующей задачи перечисления достаточно рассмотреть только графы, у которых не больше чем [ ра / 4 ] ребер. С другой стороны, решение такой задачи перечисления приводит к решению соответствующей экстремальной задачи. Варианты всех этих задач существуют также и для орграфов. [10]
Далее будем предполагать, что Г - d - граф порядка 2 и степени т с единственной максимальной системой С из s эквивалентных узлов, 1 s т - 1, заданный с помощью матрицы смежности А. [11]
Ориентированный граф называется обобщенным графом де Брейна или, кратко, d - графом порядка г, если для любой пары его вершин существует единственный путь длины г из одной вершины в другую. [12]
Аналогично, С ( х) 1п имеет при xklk коэффициент, равный числу помеченных графов порядка k, содержащих в точности п компонент. [13]
Аналогично, Сп ( х) 1п имеет при xklk коэффициент, равный числу помеченных графов порядка k, содержащих в точности п компонент. [14]
Обратно ( это было установлено независимо Финком [5] и Стюартом [14]), если ( л: 0, г / о) - точка целочисленной решетки, лежащая внутри области или на ее границе, то существует такой граф G порядка р, что X ( G) A: 0, x ( G) () Это показывает, что оценки в ( 3) для всех значений р являются наилучшими из возможных. Кроме того, Финк охарактеризовал все графы G, для которых в - каком-нибудь из четырех неравенств в ( 1) и ( 2) достигается равенство. [15]
Страницы: 1 2