Б) неориентированный граф;

В) смешанный граф

В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рисунке (б) и (в)), предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рисунке 4.1(б), имеем Г(х5) = {х1,х3, х4}, .Г(х2) = {х5} и т. д.

Поскольку Г (хi) представляет собой множество таких вершин хj- е X, для которых в графе G существует дуга (хi xj), то через Г1 (хi) естественно обозначить множество вершин хк, для которых в G существует дуга (хk хj,). Отношение

Г¹ (x_i) принято называть обратным соответствием. Для графа, изображенного на рисунке (а), имеем:

Г¹ (х₁) = {х₂,х₃}.

Г¹ (х₂)={х₁}ит.д.

Вполне очевидно, что для неориентированного графа Г¹ (х_i) = Г¹ (х_i) для всех х_j X

Деревья

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

Нижеследующие определения неориентированного дерева, как легко показать, эквивалентны друг другу.

Неориентированное дерево есть:

связный граф, содержащий п вершин и n-1 ребер, либо

Связный граф, не имеющий циклов, либо

Граф, в котором каждая пара вершин соединена одной и только одной простой цепью.

Если G = (X, А) - неориентированный граф с и вершинами, то остовным деревом (или, короче, остовом) графа G называется всякий остовный подграф графа G, являющийся деревом (в смысле приведенного выше определения). Например, если G - граф, показанный на рисунке (а), то граф на рисунке (б) является остовом графа G, как и граф, изображенный на рисунке (в). Из сформулированных выше определений вытекает, что остов графа G можно также рассматривать как минимальный связный остовный подграф графа G, где «минимальность» понимается в том смысле, что никакое собственное подмножество ребер этого остова не образует связный остовный подграф графа G.

А) Граф G; б) остов графа G; в) другой остов графа G

Понятие дерева как математического объекта было впервые предложено Кирхгофом в связи с определением фундаментальных циклов, применяемых при анализе электрических цепей.