Графы и деревья. Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно

Граф - это двойка < V, E >, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между «началом» и «концом» ребра.

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

Если ребра графа определяются упоря­доченными парами вершин, то такой граф называют ориентированным – орграфом (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указы­вающую его направление).

Если порядок ребер не имеет значения, то граф называется неориентированным.

Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (например, ребра е 4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей (например, ребро e7).

Граф без петель и параллель­ных ребер называется простым.

Если ребро е_к определяется вершинами v_i и v_j (будем обозначать этот факт следующим образом: е_k = (v_i, v_j), то говорят, что ребро е_к инцидентно вершинам v_i и v_j.

Граф G(E, U) называется конечным, если множество Е вершин конечно. Граф G(E, U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколь­кими ребрами, то такой граф называется мультиграфом. Две верши­ны е_i, е_j Î Е называются смежными, если они соединены ребром. Чис­ло ребер, инцидентных данной вершине е_i, называется локальной степенью этой вершины р(е_i). Число ребер r графа G(E, U) определя­ется выражением

Множества вершин и ребер части графа являются подмножества­ми вершин и ребер исходного графа

Полным графом называется граф у которого каждая вер­шина соединена ребрами с остальными вершинами

Обязанность графов

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

Две вершины е_i и е_j называются связанными, если существует мар­шрут из е_i в е_j.

Компонентой связности графа называется подмножество его вер­шин с инцидентными им ребрами, такое, что любая вершина свя­зана с любой другой вершиной маршрута. Например, из графа на рис. 3.5 можно выделить следующие две компоненты связанности, показанные сплошной линией.

Простой цепью, или простым путем, называется маршрут, в ко­тором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна верши­на не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной.

Цикл, проходящий по всем ребрам графа только один раз, называется эйлеровым циклом. В теории графов доказывается теорема, определяющая, содержит ли граф эйлеров цикл. Оказывается, конечный граф содержит эйлеров цикл тогда и только тогда, когда он свя­зан, и все его локальные степени вершин четные. Важной приклад­ной задачей теории графов является задача поиска в графе цикла, проходящего через каждую вершину только один раз. Такие циклы называются гамильтоновыми циклами.

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