Стягивающим или остовным деревом связного графа G наз-ся произвольный его подграф, связывающий все вершины G и являющийся деревом. Остовным лесом графа G является произвольный его подграф, содержащий все его вершины и явл. лесом. Остовной лес – послед. удаляем ребра, входящие в циклы, до тех пор, пока не будет получен ацикл. Граф. Граф наз-ся взвешенным, если каждому его ребру поставлено в соответствие число – вес ребра. Вес графа – это сумма весов всех ребер
Сущ-т эффективные алгоритмы нахождения стягивающему дерева минимального веса.
Алгоритм Краскала1.пусть n-мощность мн-ва ребер |E| следующий шаг выполнять (n-1) раз.2.включить в T ребро G наименьшего веса, облад. тем св-м, что при добавлении его в T в этом графе не образуется цикл. Исключить из G данное ребро
(G-исходный, T-искомый)
Алгоритм Примапусть V1 = {x1} - одна вершина, где x1 принадлежит V - принадлежит исходному G. Пусть E1 = пусто. След. Шаг выполнять для i=2…n. Получим дерево Si = (Vi,Ei) и с Si-1 добавлением ребра графа G наименьшего веса. Исключить данное ребро.
Бесконечным деревом назовем граф со счетным мн-вом вершин, удовлетворяющих условию: для любых 2-х вершин u, v графа сущ-т единственная uv цепь, причем длина цепи конечна.
Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д. Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.
Поиск в глубину — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все непройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.
Планарные графы
Опр: Граф наз-ся плоским, если его вершины – это точки, лежащие на плоскости и ребра графа – не пересек. на плоскости линии.
Опр: Планарным графом наз-м граф, который можно перестроить плоским.Если граф планарен, то он оказ-ся разделенным на части, включ. внеш. часть. Эти части – грани.
Опр: Грань планарного графа – это максимальный участок плоскости такой, что любые две точки могут быть соединены кривой, не пересекающей ребро графа.
Граф K3 имеет 2 грани, K4 - имеет 4 грани
Т-ма Эйлера:Если G - связный планарный граф, содержащий v (вершин), е (ребер), f (граней), то v-e+f = 2.
Док-во: Исп-м индукцию по числу ребер.
Если е = 0, то имеется 1 вершины и одна грань, поэтому верно
Если имеется е = 1, то v = 2, f = 1, и тоже верно
Предположим, что т-ма верна и для произвольном планарного связного графа у которого k ребер.
Пусть имеется Gk+1 с |k+1| - ребрами.
Удалим одно ребро и получим Gk с k ребрами и покажем, что для любого Gk+1 т-ма выполняется.
Пусть Gk+1 не имеет циклов, будем двигаться по пути до тех пор, пока не достигнем вершины из которой нет другого выходного ребра. Это воз-но в случае когда в Gk+1 нет циклов. Найденная вершина имеет степень 1, удалим вершину и ребро инцидентное ей, число граней не изменяется граф останется связным и планарным и будет содержать k ребер.
Если в Gk+1 есть циклы, удалим из цикла ei с инцидентными вершинами ui и vi, сами вершины оставим согласно теореме все еще имеется путь из ui в vi, так что граф остается связным и планарным. Он будет иметь *-ребер и след. Теорема вып-ся. Поскольку ei входит в цикл, оно разделяет две грани и значит при удалении этого ребра, удалится и грань, поэтому значение v-e+f=2 не измелось и ф-ла для Gk+1 справедлива.
Т-ма: Полный двудольный граф K33 не является планарным
Док-во: Используем метод приведения к абсурду
Предположим что K33 планарный. Если K33 планарный, то 6-9+f=2 f=5
Пусть А и В неперсек. мн-ва вершин, формир-е мн-во V- вершин графа V= АUВ, А ∩ В = пусто. Если начать путь из А и не повторять ребра, то можно попасть в вершину из В, затем в вершину из А прежде чем завершить цикл. Любой цикл в K33 представляет собой путь, длина которого по меньшей мере равна 4. Поэтому каждая грань определена циклом в котором не менее 4-х ребер, то сущ-т сумма всех ребер всех граней больше 4f, но каждое ребро считывается не более 2-х раз, поскольку оно явл. Границей не менее 4-х граней. Значит сумма ребер всех граней должна быть меньше 2e, т. об получим 4f меньше или равно 2е, т. е. f меньше или равно 4, 5 а это противоречие
Лемма:В произвольном связ. планарном G с количест. V больше или равно 3 имеет место нер-во:
3v - е больше или равно 6
Док-во: Если G не имеет циклов, то в нем ребер меньше чем вершин е <=v, учитывая что v>=3, 2v - 6 больше или равно 0 получим е <=v+ 2v - 6 или 3v - 6 или 3v-е>=6
Если G содержит цикл, то просуммируем ребра, огранич-е грани, поскольку граница каждой грани содержит не менее трех ребер, то сумма всех ребер, всех граней должна быть больше 3f и одновременно любое ребро может быть границей не более двух граней, кол-во ребер меньше 2е след-но 3f<=2е. Учитывая, что v - е +f = 2 получим
Т-ма: Граф К5 не является планарным.
Док-во: Граф К5 имеет пять вершин и 10 ребер след-но 3v - е = 5, а по пред. лемме этот граф не планарный
Критерий планарности
Подразбиением ребра uv наз-т его замену на два ребра uw и wv
Два графа гомиоморфны, если они могут быть получены из одного и того же графа подразбиением ребер. Гомиоморфные плоские графы имеют одинакое кол-во граней.
Теорема Понтрягина и Куратовского
Граф планарный тогда, когда он не содержит подграфа гомиоморфного К33 или К5
