8. Эйлера и гамильтонов графы.
Эйлеров цикл – цикл, содержащий все рёбра исходного графа (каждое ребро используется ровно 1 раз).
Эйлеров граф – связный граф, содержащий эйлеров цикл.
Теорема Эйлера или критерий существования в графе эйлерового цикла:
Связный граф G является эйлеровым тогда и только тогда,
когда степени всех его вершин четны
Следствие №1. Для связного графа G множество ребер можно разбить на простые циклы, если граф эйлеров.
Следствие №2. Для того чтобы связный граф G покрывался единственной эйлеровой цепью, необходимо и достаточно, чтобы он содержал ровно 2 вершины с нечетной степенью. Тогда цепь начинается в одной из этих вершин и заканчивается в другой.
Эйлерова цепь – цепь с концевыми вершинами (a, b), начинающаяся в вершине a, заканчивающаяся в вершине b и содержащая каждое ребро исходного графа ровно 1 раз.
Гамильтонов цикл – простой цикл, содержащий каждую вершину графа.
Гамильтонов граф – граф, содержащий гамильтонов цикл.
Достаточные условия существования гамильтонова цикла в графе
Теорема Дирака
Если число вершин графа p 3 и для любой вершины выполняется условие
vi,
i
=
;
deg
vi
,
то граф G – гамильтонов
Теорема Оре
Если число вершин графа p 3 и для любых двух несмежных вершин u и v выполняется неравенство:
deg u + deg v p, то граф G – гамильтонов
9. Плоские и планарные графы.
Плоским - называется такой граф G у которого, вершины точки плоскости, а ребра непрерывные плоские линии без пересечений и самопересечений, причем соединяющие вершины так, что никакие два ребра не имеют общих точек, кроме инцидентных им обоим вершин.
Планарный это граф, который изоморфен плоскому.
О планарных графах говорят, что они имеют плоскую укладку.
Жорданова кривая это непрерывная спрямляемая линия, не имеющая самопересечений.
Гранью плоского графа называется максимальное по включению количество точек плоскости, каждая пара которых может быть соединена Жордановой кривой, не пересекающей ребра графа.
Граница грани это множество вершин и ребер, принадлежащих грани.
Теорема Эйлера для плоского графа.
Для
любого связного графа G,
являющегося плоским справедливо
соотношение: p – q
+ f = 2, где p
количество вершин, q
количество ребер, f
количество граней плоского графа.
.
Критерии планарности
Критерий Понтрягина-Куратовского (критерий планарности). Граф планарен тогда, когда он не содержит подграфов гомеоморфных K5 или K3,3.
Критерий Вагнера. Граф планарен тогда, когда он не содержит подграфов, стягиваемых K5 или K3,3 (по методу операции стягивания).
Примеры: Граф Петерсена
Граф G1 – не планарен, т. к. он содержит подграф G2, гомеоморфный K3,3