35. Поиск маршрутов в графах.
Алгоритм
(Тэрри) поиска
пути в связном графе, из вершины vi в
вершину vj,
где vi
vj.
Исходя из вершины vi осуществлять последовательный переход от каждой достигнутой вершины к смежной ей вершине, по следующим правилам:
1. идя по произвольной дуге, всякий раз отмечать направление, в котором оно было пройдено;
2. исходя из некоторой вершины vk, всегда следовать только по дуге, которое не было пройдено или было пройдено в противоположном направлении;
3. для всякой вершины vk, отличной от vi, отмечать первую заходящую в vk дугу, если вершина vk встречается в первый раз;
4. исходя из некоторой вершины, vk, отличной от вершины vi, по первой заходящей в vk дуге идти лишь тогда, когда нет других возможностей.
Путь в орграфе из вершины vi в вершину vj, где vi ` vj , называется минимальным, если он имеет минимальную длину среди всех путей орграфа из vi в vj.
36.Деревья, свойства деревьев. Лес.
Граф называется деревом, если он является связным и не имеет циклов. Любые две различные вершины дерева можно соединить единственной (и притом простой) цепью. Число дуг дерева на единицу меньше числа его вершин. Пусть G – дерево. Тогда любая цепь в G является простой. Если какую-нибудь пару несмежных вершин дерева соединить дугой, то полученный граф будет содержать ровно одну цепь. Граф, все компоненты связности которого являются деревьями, называется лесом.
37.Остовное дерево, минимальное остовное дерево. Остовным деревом (остовом или каркасом) связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Замечание. Остовное дерево графа не единственно. Число дуг произвольного неорграфа G, которое надо удалить для получения остова, не зависит от последовательности их удаления и равно m – n + k, где m – число дуг, n – число вершин, k – число компонент связности графа G. Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
38.Эйлеровы графы и циклы.
Эйлеровым
путем в
графе называется путь, содержащий все
ребра графа. Эйлеровым
циклом в
графе называется цикл, содержащий все
ребра графа. Связный
граф 
называется эйлеровым,
если существует замкнутая цепь,
проходящая через каждое его ребро.
Такая цепь называется эйлеровой
цепью. Отметим,
что в этом определении требуется, чтобы
каждое ребро проходилось только один
раз. Если снять ограничение на замкнутость
цепи, то граф называется полуэйлеровым,
при этом каждый эйлеров граф будет
полуэйлеровым. Если
граф
обладает
эйлеровым циклом, то он является связным,
а все его вершины — четными.
39. Гамильтоновы графы и циклы.
Маршрутом (или путем) в графе G называется чередующаяся последовательность вершин и ребер v0, e1, v1, …, vt−1, et, vt+1, в которой ei = vi−1vi (1 ≤ i ≤ t). Такой маршрут кратко называют (v0, vt)-маршрутом и говорят, что он соединяет v0 c vt; в свою очередь вершины v0, vt — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v0, v1, …, vt своих вершин. Если v0=vt, то (v0, vt)-маршрут называется замкнутым. Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, быть может, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром). Гамильтоновой цепью графа называется его простая цепь, которая проходит через каждую вершину графа точно один раз. Цикл графа, проходящий через каждую его вершину, называется гамильтоновым циклом. Граф называется гамильтоновым, если он обладает гамильтоновым циклом. Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (Hamilton W.), который в 1859 году предложил следующую игру-головоломку: требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вернуться в начальную вершину.