Два - граф
Cтраница 4
Граф называется полным, если любые две его различные вершины соединены ребром. Два графа G и Я изоморфны, если существует взаимно однозначное отображение ( называемое изоморфизмом) множества вершин графа G на множество вершин графа Н, сохраняющее смежность. Автоморфизмом графа О называется изоморфизм графа G на себя. На рис. 8.4 представлен граф G4 и его автоморфизм ср. [46]
По определению, граф называется пустым, если пусто множество его верпшп. Наконец два графа называются непересекающимися, если пусто их пересечение. [47]
Два графа, вершины которых помечены, считаются тождественными ( неразличимыми) в том и только в том случае, когда любые две вершины, помеченные одинаково в обоих графах, имеют одинаковое число инцидентных им ребер. Так, два графа могут считаться различными, даже еслч они изоморфны. [48]
Два графа G4 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в Glf равно числу ребер, соединяющих соответствующие вершины в Gz. Так, два графа, изображенные на рис. 2.5, изоморфны при соответствии и I, v т, w п, х р, у q, z - г. Заметим, что эти графы имеют по шесть вершин - другие точки пересечения ребер вершинами не являются. [49]
Мы можем, удалив х, образовать из G новый 2-граф двумя способами, полагая либо Р R, QS, либо P S, Q - R. Обозначим эти два графа через G, и Оя соответственно. [50]
Причина, по которой введено ограничение на & ( а именно, Ь 4), ясна из рис. V. На нем изображены два графа О и Н, такие, что, удаляя из них произвольное ребро, мы получаем, с точностью до изоморфизма, один и тот же подграф. [51]
Ясно, что непомеченный граф может быть пронумерован п способами, но при этом некоторые из них могут совпадать. Следовательно, эти два графа являются одинаковыми. [52]
Но есть и другой путь, требующий всего п 11 состояний: на ленте непосредственно пишется п единиц, после чего, как в примере 3.2, этот массив удваивается. Схематически: мы соединяем два графа переходов, отождествляя вершину 1 из примера 3.2 с вершиной п из графа машины, пишущей п единиц на пустой ленте. [53]
 |
Два дерева с одинаковым разбиением. [54] |
Не существуют графические разбиения, в которых все слагаемые различны. Для любого p s2 существуют точно два графа с р вершинами, в которых только два слагаемых разбиения равны, и эти графы являются дополнительными. [55]
Рид [6] показал, как можно подсчитать число само дополнительных графов, первым применив теорему де Брейна [2] к подсчету графов с точностью до их взаимной дополнительности. Чтобы описать метод Рида, будем называть два графа эквивалентными относительно дополнительности, если они изоморфны или один из них изоморфен дополнению другого. Выразим теперь эту эквивалентность на языке степенной группы. [56]
Рид [6] показал, как можно подсчитать число самодополнительных графов, первым применив теорему де Брейна [2] к подсчету графов с точностью до их взаимной дополнительности. Чтобы описать метод Рида, будем называть два графа эквивалентными относительно дополнительности, если они изоморфны или один из них изоморфен дополнению другого. Выразим теперь эту эквивалентность на языке степенной группы. [57]
Страницы: 1 2 3 4