Графы. 
Графы и матрицы, связанные с графами

Основные определения

Пусть V — произвольное множество, V2 — множество всех его двухэлементных подмножеств, т. е. множество неупорядоченных пар {а, b}, где а, b V. Пара (V, E), где Е — произвольное подмножество V2, называется графом (неориентированным графом). При этом элементы множества V называются вершинами графа, элементы множества E — ребрами. Множества вершин и ребер графа G обозначаются символами V (G) и E (G) соответственно. Вершины и ребра графа называются его элементами.

В дальнейшем буду рассматривать только конечные графы, т. е. множество E предполагается конечным. Число | V (G) | вершин называется его порядком и обозначается через |G|. Если |G| = п, |E (G)| = т, то G называют (п, т)-графом.

Говорят, что две вершины u и v смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если е = {u, v} - ребро, то вершины u и v называют его концами. В этом случае также говорят, что ребро е соединяет вершины u и v. Такое ребро обозначается символом uv .

Два ребра называются смежными, если они имеют общий конец.

Вершина е и ребро v называются инцидентными, если v является концом ребра е, и не инцидентными в противном случае.

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

Это (5, 6)-граф, V (G) = {1, 2, 3, 4, 5}, E (G) =^[1]. Вершины 1 и 2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро {1, 2} инцидентны. Иногда в графах допускается наличие петель, т. е. ребер {а, а} (рис. 2), и кратных ребер, т. е. ребро {а, b} учитывается несколько раз (рис. 3). Мы будем рассматривать графы без петель и кратных ребер.

Ориентированный граф — это пара (V, А), где V — множество вершин, А — множество ориентированных ребер (или дуг), т. е. упорядоченных пар (u, v), где u, v V. При этом и называется началом дуги, v — концом. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу (рис. 4).