6.1. Основные понятия

Графом G (в широком понимании) называется любая пара (V,U), где V = {v1, v2, ... } – множество элементов любой природы, а U = {u1, u2, ... } – семейство пар элементов из V, причем допускаются пары вида (vi, vj) и одинаковые пары вида (vi, vi).

Если пары в U рассматриваются как неупорядоченные, то граф называется неориентированным, если как упорядоченные, то граф называется ориентированным (орграфом).

Элементы множества V называются вершинами графа, а пары из U в неориентированном графе называются ребрами, а в орграфе

– ориентированными ребрами, или чаще дугами.

Говорят, что ребро u = (vi, vj) в неориентированном графе соединяет вершины vi и vj, а в ориентированном графе дуга u = (vi, vj) идет из вершины vi в вершину vj.

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

Пара вида (vi, vi) называется петлей в вершине vi. Если пара (vi, vj) встречается в U более одного раза, то говорят, что (vi, vj) –

кратное ребро.

Говорят, что вершины vi и vj смежны в графе G = (V, U), если в

U входит пара (vi, vj) или (vj, vi). Говорят, что ребро (дуга) (vi, vj) инцидентно вершинам vi и vj. В этом смысле, граф можно задать

как совокупность двух множеств: вершин V и ребер U, между которыми определено отношение инцидентности. Каждое ребро u из U инцидентно ровно двум вершинам vi, vj, которые оно соединяет. При этом вершина vi и ребро u называются инцидентными друг другу, а вершины vi и vj называются смежными. Два различных ребра графа называются смежными, если они имеют, по крайней мере, одну общую вершину.

Степенью вершины v неориентированного графа G называется число ребер, инцидентных v, при этом степень вершины будем обозначать через Stv. Вершина степени 0 называется изолированной вершиной. Вершина степени 1 называется висячей, или концевой вершиной.