Граф - порядок
Cтраница 2
Кроме тривиального случая одной вершины, все графы небольших порядков имеют неединичные группы. Согласно Каньо, граф порядка 6, изображенный на рис, 15.1.4, является графом наименьшего порядка с единичной группой. [16]
Кроме тривиального случая одной вершины, все графы небольших порядков имеют не-едннпчные группы. Согласно Каньо, граф порядка 6, изображенный на рис. 15.1.4, является графом наименьшего порядка с единичной группой. [17]
 |
Граф и три его остова. [18] |
Число помеченных деревьев может быть быстро получено как простое следствие этого результата. Матрицей смежности А A ( G) [ % ] помеченного графа G порядка р называется ( р X р) - матрица, в которой ati 1, если вершины i и / смежны, и df ] 0 в противном случае. Следовательно, существует взаимно однозначное соответствие между помеченными графами порядка р и симметрическими двоичными ( р X р) - матрицами с нулевыми диагональными элементами. [19]
 |
Граф и три его остова. [20] |
Число помеченных деревьев может быть быстро получено как простое следствие этого результата. Матрицей смежности А A ( G) [ а / ] помеченного графа G порядка р называется ( Р р) - матрица, в которой ati 1, если вершины i и / смежны, и atj 0 в противном случае. Следовательно, существует взаимно однозначное соответствие между помеченными графами порядка р и симметрическими двоичными ( JD X р) - матрицами с нулевыми диагональными элементами. [21]
Мы ответим на легкий вопрос, незначительно обобщив задачу следующим образом: найти число помеченных графов с данным числом вершин и ребер. Пусть Gp ( x) - многочлен, у которого коэффициент при xk равен числу помеченных графов порядка р, имеющих ровно k ребер. Такой многочлен обычно называется производящей функцией для помеченных графов с данным числом вершин и ребер. [22]
 |
Шесть различных распределений пометок в графе. [23] |
Мы ответим на легкий вопрос, незначительно обобщив задачу следующим образом: найти число помеченных графов с данным числом вершин и ребер. Пусть Gp ( х) - многочлен, у которого коэффициент при xk равен числу помеченных графов порядка р, имеющих ровно k ребер. Такой многочлен обычно называется производящей функцией для помеченных графов с данным числом вершин и ребер. [24]
 |
Неразделимые графы.| Разделимые графы. [25] |
Непустое множество R С X называется множеством сочленения R, если подграф, порожденный множеством ( XR), несвязен. В случае когда R сводится к одной вершине х0, снова получим точку сочленения. Если граф несвязен, пустое множество 0 рассматривается как множество сочленения. Множеством изоляции графа порядка п называют любое множество из п - 1 его вершин. [26]
Граф, не имеющий ребер, называется пустым. Если любые две ( различные) точки графа соединены ребром, то граф называется полным. Число точек графа называется его порядком, а число ребер - его классом. Таким образом, на рис. 91 представлен граф порядка десять и класса пятнадцать. [27]
Полученные в работе результаты, по-видимому, допускают обобщение на случай d - графов произвольного порядка. Это следует из общего его замечания о том, что автоморфизмы d - графа Г однозначно определяются их действием на узлах. Этим обеспечивается изоморфное вложение Aut Г в Еш. Данный факт следует из того, что ограничение d - графа порядка г на множество неподвижных вершин относительно его автоморфизма также будет б / - графом порядка г с числом вершин, равным ( см. [3]) г-и степени числа неподвижных узлов. [28]
 |
Четные графы пятого порядка и их числа симметрии. [29] |
Раскрашенный граф состоит из графа G с множеством вершин V и такого отношения эквивалентности на множестве F, что любые смежные вершины не эквивалентны, k классов эквивалентности рассматриваются как различные цвета и граф G называется - раскрашенным. Два - раскрашенных графа изоморфны, если существует взаимно однозначное соответствие между их множествами вершин, которое сохраняет не только смежность, но и цвета. Заметим, что цвета не закреплены постоянно, а являются взаимозаменяемыми. Данный граф может быть / с-раскрашен многими способами. Например, все 3-раскраски некоторого помеченного графа порядка 6 показаны на рис. 1.5.1, где буквы а, Ъ и с обозначают цвета, а натуральные числа обозначают пометки. [30]
Страницы: 1 2