КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Перечисление графов
Свойства деревьев Деревья
Определение. Связный граф, не содержащий циклов, называется деревом (рисунок 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, в то время как различных неизоморфных четырехвершинных графов без пометок существует всего .
Если через обозначить число неизоморфных -вершинных графов с ребрами, то:
В общем случае количество неизоморфных графов , находятся с помощью теории перечисления конфигураций, созданной Д. Пойа.
Дата добавления: 2014-11-20; Просмотров: 2261; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |