Перечисление графов
Свойства деревьев
Деревья
Определение.Связный граф, не содержащий циклов, называется деревом (рисунок 6.65).
Рисунок 6.65 – Дерево
Несвязный граф, не содержащий циклов, называется лесом.
Пример.На рисунке 6.66 приведен трехкомпонентный лес. Первую компоненту образует дерево с вершинами 1,2,3,4, вторую – 5,6,7,8,9, третью – 10,11.
Рисунок 6.66 – Лес
Теорема 6.9. Всякое дерево содержит ребер, где – число вершин.
Теорема 6.10. Всякий лес содержит ребер, где – число компонент связности.
Теорема 6.11. Любые две вершины дерева соединены точно одной простой цепью.
Теорема 6.12. Если в дереве любые две вершины соединить ребром, то в графе появится один цикл.
Определение.Граф называется помеченным, если его вершинам присвоены фиксированные метки, например, номера .
Два помеченных графа одинаковы (не различаются), если их вершины помечены одной системой меток и существует изоморфизм одного графа на другой, при котором сохраняются метки всех вершин.
Пример.На рисунке 6.67 изображены все помеченные графы с числом вершин ; их количество равно 8.
Рисунок 6.67
Количество (неориентированных) помеченных графов (простых с вершинами и ребрами) равно числу сочетаний из множества различных неориентированных пар вершин по числу ребер .
,
Суммируя числа по всем возможным количествам ребер от случая безреберного графа до случая полного графа с вершинами, получаем число всех помеченных графов с вершинами:
Число неизоморфных графов без пометок (простых, неориентированных) найти значительно труднее. Среди восьми графов на рисунке 3 без учета пометок можно указать только четыре попарно неизоморфных друг другу, например, в квадратах 1, 2, 7, 8. Следовательно, , что вдвое меньше числа помеченных графов. Число помеченных четырехвершинных графов равно 64, в то время как различных неизоморфных четырехвершинных графов без пометок существует всего .
Если через обозначить число неизоморфных -вершинных графов с ребрами, то:
В общем случае количество неизоморфных графов , находятся с помощью теории перечисления конфигураций, созданной Д. Пойа.