ДМ

26.Задача об остове экстремального веса. Алгоритм Прима.

27.Эйлеровы графы и циклы. Алгорити Флери. Гамильтоновые графы и циклы. Примеры.

Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро. Такая цепь называется эйлеровой цепью(цикл).

Эйлеров граф – граф, который содержит эйлеров цикл. Связный граф является эйлеровым, если степени всех вершин четные. Чтобы граф обладал эйлеровой цепью, надо чтобы было 2 вершины нечетной степени.

Простая цепь(цикл) в графе G называется гамильтоновой, если она (он) проходит через каждую вершину графа G. Граф называется гамильтоновым, если содержит гамильтонов цикл.

28. Планарные графы. Укладка графа. Теорема Эйлера, теорема Понтрягина-Куратовского. Понятие искаженности и толщины непланарных графов.

Планарный граф - вершины которого являются точки плоскости, а ребра непрерывные линии и никакие два ребра не имеют общих точек, кроме инцидентных им обоим вершины.

Теорема Эйлера – для всякого связного планарного графа с р вершинами, q ребрами и r гранями: p-q+r=2.

Теорема Понтягина-Куротовского – Граф планарен тогда и только тогда, когда он не содержит подграфов гомеоморфных K5 и K3,3.

Наименьшее число ребер удаления которых приводит к планарному графу называют искаженностью

sk(G)= 2 − 3 + 6, ≥ 3

Толщина графа t(G) называется наименьшее число планарных подграфов графа G, объединение которых дает сам граф. ( ) = [ +76 ]

( ) ≥ [3 −6] t

29.Алгоритм укладки графа на плоскости. Примеры.

30.Раскраски графов. Хроматические графы. Алгоритм последовательной раскраски графа. Примеры.

Хуетень какая-то

Раскраска графа называется такое приписывание цветов его вершинам, что никакие 2 смежные вершины не получают одинакового цвета. Хроматическое число – минимальное число цветов для правильной раскраски.

Алгоритм раскраски – 1 шаг: Произвольной вершине присваивается цвет 1. 2 шаг: если v1,v2..vi раскрашены к цветами, где к – это 1,2,3…I, то новой произвольно взятой вершине vi+1 приписывается минимальный цвет, неиспользованный при раскраске вершин его окружения.