4. Основы теории графов

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

Пусть дано множество V = {v₁, v₂, …, v_n} и в V определено семейство U = {u₁, u₂, …, u_m} пар элементов u_{k =} {v_i, v_j}, (k = 1, m) произвольной кратности и упорядочения. Пара {V, U} именуется: граф. Графы, как правило, обозначают прописными латинскими буквами, например, G, H. Принято также писать G(V, U) для того, чтобы определить некото­рый конкретный граф G.

Элементы v₁, v₂, …,v_n называются вершинами графа, а пары u_{k =} {v_i, v_j}, (k = 1, m) — ребрами.

Определению графа можно дать следующую интер­претацию. Пусть имеем описание графа:

G(V,Е) = {{ v₁, v₂, …, v₆}, { { v₁, v₃ }, v₅, v₁, {v₃, v₄},

v₂, v₃, {v₃, v₃ }}}.

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

v₁ v₄ v₂

V₆

v₃ v₅

Рисунок 4.1

Если этот порядок не существенен, то ребро на­зы­вается неориентированным, в противном случае ребро на­зыва­ется ориентированным. Ориентированные ребра назы­ва­ются также дугами.

Для ориентированного ребра определены понятия на­чальной и конечной вершины. Начальная вершина запи­сы­вается в начале пары вершин, определяющих дугу,а коне­чная — в конце. Так на рисунке 4.1 ребра v₅, v₁ и v₂, v₃ являются дугами. Они представлены упорядоченными пара­ми вершин и, в связи с этим, обозначены так же, как обозна­чаются упорядоченные множества.

Ребра {v₁, v₃}, {v₃, v₄} неориентированы. Для любого неориентированного ребра полагают, что {v_i, v_j} = {v_j, v_i} так же, как и в случае неупорядоченных множеств. Ребро {v_i, v_i} называется петлей. На рисунке 4.1 имеем петлю {v₃, v₃}. Петли обычно не ориентированы.

Граф, у которого все ребра неориентированы, назы­вается неориентированным. Неориентированное ребро мо­жет быть эквивалентно паре ориентированных ребер, если это возможно по условию задачи.

Граф, у которого все ребра ориентированы, называется ориентированным или орграфом.

На рисунке 4.1 приведен смешанный граф, т.е. содер­жащий как ориентированные, так и неориенти­рованные реб­ра и петлю.

Многие теоремы и определения в теории графов могут быть отнесены как к ориентированным, так и к неориентированным графам. В таких случаях для обозначения ребер применяют круглые скобки, например, ребро {v₃, v₄} в графе рисунок 4.1 можно обозначать (v₃, v₄) либо (v₄, v₃), а ребро v₅, v₁ — соответственно как (v₅, v₁), указав при этом, что данное ребро представляет дугу. Принято также обозначение всех ребер круглыми скобками как в случае ориентированных графов, так неориентированных, если совершенно ясно о каком из типов этих графов идет речь в тексте.

Некоторые вершины графа G могут не войти в список пар. Такие вершины именуются изолированными. В рас­смотренном примере это вершина v₆. Граф, у которого все вершины изолированы, именуется нуль‑графом. Множество ребер такого графа пусто.

Антиподом нуль‑графа является полный граф. Ребрами полного графа являются всевозможные пары его вершин.

Как в случае ориентированного графа, так и в случае неориентированного — говорят, что ребро инцидентно паре определяющих его вершин.

Одной и той же паре вершин можно поставить в со­от­ветствие множество инцидентных ребер. Такие ребра назы­ваются кратными. Так на рисунке 4.2 представлена пара ве­ршин (v_i, v_j), инцидентных трем различным ребрам u₁, u₂, u₃. Одно из них направлено, а два — нет.

u₁

v_i u₂ v_j

u₃

Рисунок 4.2

Граф называется плоским, если он может быть изоб­ражен на плоскости так, что все пересечения ребер есть его вершины. Так графы, представленные на рисунках 4.1 и 4.2 плоские. Примеры не плоских графов будут рассмотрены ниже в разделе 4.3.

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

Граф H называется частью графа G или частичным графом H  G, если множество его вершин V(H) содержится в множестве вершин V(G) графа G и все ребра H являются ребрами G. Частным, но важным типом частичных графов являются подграфы.

Пусть A — подмножество множества вершин V графа G. Подграф G(A) графа G есть такая часть графа, множеством вершин которого является A, а ребрами — все ребра из G, оба конца, которых лежат в A.

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