62. Графы. Способы задания графов.

Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

Граф можно задать графически, аналитически и с помощью матрицы. Графы принято изображать рисунками, состоящими из точек, называемыми вершинами, и линий, называемыми дугами, соединяющими две вершины графа. Форма дуг несущественна, важен только сам факт соединения вершин. Дуги могут пересекаться, но точки пересечения не являются вершинами графа. Если дуги имеют направление, отмеченное стрелкой, то такие графы называются ориентированными или орграфами. Дуги графа часто называют ребрами. Дуги, соединяющие две одинаковые вершины не ориентированного графа, называются кратными. Дуга, выходящая из вершины и входящая в нее, называется петлей. Дуги орграфа называются параллельными, если они соединяют две одинаковые вершины графа и имеют одно направление. Дуги орграфа называются противоположными, если они соединяют две одинаковые вершины графа и противоположно направлены. Две вершины графа называются смежными, если они соединены дугой, иначе они называются несмежными. Вершина графа (орграфа) называется изолированной, если она не соединяется дугой с другими вершинами графа. Граф с кратными дугами и петлями называется псевдографом. Ориентированный псевдограф соответственно имеет параллельные дуги и петли.

63. Формула Эйлера.

Граф, который можно нарисовать так, чтобы его рёбра не пересекались, называется плоским.

Нарисованный без пересечений плоский граф разбивает плоскость на куски. Такие куски называются гранями. Обозначим число вершин графа через В, число рёбер через Р, число граней через Г, тогда справедлива Формула Эйлера:

В - Р + Г = 2

64. Графы к3,3 и к5,5. Теорема.

Граф К3,3 Граф К5

65. Плоские графы. Теорема о плоских графах (без доказательства).

Плоский граф — граф, уложенный на плоскость. Граф называется планарным, если он изоморфен некоторому плоскому графу. Граф укладывается на некоторой поверхности, если его можно на ней нарисовать без пересечения ребер. Уложенный граф называется геометрическим, его вершины — это точки плоскости, а ребра — линии на ней. Области, на которые граф разбивает поверхность, называются гранями.

Граф К3,3 Граф К5

Теорема: граф G содержит подграф, гомеоморфный K5 или K3,3, невозможно разложить на плоскости. Верно и обратное.

66. Эйлеровые графы. Теорема о Эйлеровых графах. Гамильтоновы графы.

Цепь называется эйлеровой, если она является простой и проходит по всем ребрам графа. Эйлеровым циклом называется простой цикл, проходящий по всем ребрам. Граф, имеющий эйлеровый цикл, называется эйлеровым графом.

Теорема: Для того чтобы связный граф был эйлеровым необходимо и достаточно, чтобы степени всех вершин его были четными.

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