На этом шаге мы приведем некоторые понятия теории графов.
По поводу терминологии в теории графов уместно привести цитату из книги авторитетного специалиста Ф.Харари [1, с.21]: "Большинство специалистов по теории графов употребляют в книгах, статьях и лекциях свою собственную терминологию... Даже само слово "граф" не является священным. Некоторые авторы действительно определяют "граф" как граф, другие же имеют в виду такие понятия как мультиграф, псевдограф, ориентированный граф или сеть. Нам кажется, что единобразие в терминологии теории графов никогда не будет достигнуто, но, может быть, оно и не к чему".
Вначале дадим неформальное определение графа.
Ориентированным графом называется пара (V,E), где V - множество вершин, а E - множество ребер; элементами множества E являются упорядоченные пары вершин.
Неориентированным графом называется пара (V,E), где V - множество вершин, а E - множество ребер; элементами множества E являются неупорядоченные пары вершин.
Формальное определение неориентированного графа звучит так. Пусть V - непустое множество, V2 - множество всех его двухэлементных подмножеств. Пара (V,E), где E - произвольное подмножество V2, называется неориентированным графом.
Дадим теперь формальное определение ориентированного графа. Пусть V - непустое множество, VxV - его декартов квадрат. Пара (V,A), где A - произвольное подмножество VxV, называется ориентированным графом.
Элементы множества A называются ориентированными ребрами или дугами. Если (v1,v2) - дуга, то вершины v1 и v2 называются ее началом и концом соответственно.
Граф (V,E) можно рассматривать как двухместное (бинарное) отношение E на множестве V, которое определяется как множество упорядоченных (или неупорядоченных) пар элементов множества V.
Говоря о бинарных отношениях как о графах, просто имеют в виду возможность их визуального представления и использования характерных для графов методов и терминологии. Граф обычно изображается на плоскости в виде множества точек, соответствующих вершинам, и соединяющих их линий, соответствующих ребрам. Вершины могут располагаться на плоскости произвольным образом. Причем неважно, является ли ребро, соединяющее две вершины, отрезком прямой или кривой линии, т.к. важен сам факт соединения двух данных вершин ребром.
Если требуется различать вершины графа, их нумеруют или обозначают разными буквами. В изображении графа на плоскости могут появляться точки пересечения ребер, не являющиеся вершинами. Ниже, чтобы отличать вершины от таких точек, будем изображать вершины кружками.
Примером геометрического представления графа может служить схема линий метрополитена.
Число вершин графа G называется его порядком. Граф порядка N называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, ...,N.
В случае неориентированного графа две вершины, между которыми есть ребро, называются смежными. Более формально, говорят, что две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае.
Назовем два ребра смежными, если у них есть общая вершина.
Вершина v и ребро e называются инцидентными, если v является концом ребра e (т.е. e=uv), и не инцидентными в противном случае.
Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.
Простой путь в графе - это последовательность смежных ребер (V1,V2) (V2,V3) ... (Vk-1,Vk), таких, что все Vi кроме, быть может, V1 и Vk различны. Заметим, что для ориентированного графа это определение означает, что направления ребер вдоль всего пути согласованы.
Число ребер, составляющих путь, называется его длиной.
Простой путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом.
Неориентированный граф называется связным, если любые две его вершины можно соединить путем.
Ориентированный граф связен, если связен граф, полученный из него путем удаления ориентации его ребер.
В связном неориентированном графе можно ввести понятие расстояния между вершинами. Расстояние между вершинами U и V определяется как минимальная длина пути между U и V.
Граф H называется подграфом графа G, если все вершины и ребра графа H являются в то же время соответственно вершинами и ребрами графа G. В этом случае говорят также, что H содержится в G.
Рассмотрим некоторое семейство подграфов графа G. Граф Hmax из этого семейства называется максимальным, если он не содержится ни в каком другом графе из рассматриваемого семейства.
Неориентированный связный граф называется деревом, если он не содержит циклов.
Дерево с выделенной вершиной называется корневым деревом, а сама выделенная вершина - корнем.
Максимальный древесный подграф называется остовом графа, а максимальный связный подграф - его связной компонентой. В связном графе имеется единственная связная компонента, совпадающая с самим графом.
Два графа G и H изоморфны, если существует взаимно однозначное отображение (называемое изоморфизмом) множества вершин графа G на множество вершин графа H, сохраняющее смежность. Автоморфизмом графа G называется изоморфизм графа G на себя.
(1)Харари Ф. Теория графов. - М.: Мир, 1973. - 300 с.
Со следующего шага мы начнем рассматривать способы представления графов.
