Основные понятия теории графов. Изображение графа в виде точек и линий – это лишь наиболее наглядный способ их представления

Изображение графа в виде точек и линий – это лишь наиболее наглядный способ их представления. Формально граф определяется так: граф – это пара объектов G = (V, E), где V – некоторое конечное множество, Е – отношение на V: E ÍV´V. V – множество вершин, E – множество ребер.

Ребро принято обозначать либо как элемент Е: e₁, …, e_m, e_j ÎE, либо указанием его начальной и конечной вершины (v_i, v_j). Второе обозначение не всегда однозначно, например, в задаче о мостах обозначению (v₁, v₃) соответствуют два различных ребра.

Def. Графом без кратных ребер называется граф, в котором для любых i, j существует единственное ребро e_k = (v_i, v_j). Граф с кратными ребрами называется еще мультграфом.

Def. Пусть u, v – вершины, е = (u, v) – соединяющее их ребро. Тогда вершина u и ребро e инцидентны друг другу (также как и v и е). Два ребра, инцидентные одной вершине называются смежными. Две вершины, инцидентные одному ребру также называются смежными.

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

Def. Граф называется полным, если любые его две вершины смежны, E = V´ V. 0-граф – граф без ребер. Изолированная вершина – не смежная ни с одной другой вершиной.

Def. Дополнение графа , где = (V´V) \ E.