§ 2.2. Отношения и характеристики элементов графа

Между элементами графа существуют отношения инцидентности и смежности.

Ребро и вершина инцидентны друг другу, если вершина является концевой вершиной данного ребра, и не инцидентны в противном случае.

Две вершины смежны, если они инцидентны одному и тому же ребру.

Рёбра смежны, если они инцидентны одной вершине.

Заметим, что отношение смежности существует между однотипными элементами графа, а отношение инцидентности – между разнотипными.

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

Для неориентированных графов существует понятие «окружение вершины». Пусть G = (V,E) – неориентированный граф, v_i – некоторая его вершина (v_iV). Окружением вершины v_i называется множество смежных ей вершин графа G; обозначается таким образом: N_G(v_i). Мощность множества N_G(v_i) называется степенью вершины v_i.

Для орграфов существуют понятия «полустепени исхода вершины» и «полустепени захода вершины».

Пусть G = (X,A) – ориентированный граф, x_i – некоторая его вершина (x_iX). Полустепенью исхода вершины x_i называется мощность множества концевых вершин тех дуг, для которых вершина x_i является начальной. Обозначается полустепень исхода _О(x_i). Полустепенью захода вершины x_i называется мощность множества начальных вершин тех дуг, для которых вершина x_i является конечной. Обозначается полустепень захода _t(x_i).

§ 2.3. Способы задания графов.

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

§ 2.3.1. Задание графов через соответствие

Пусть G = (Х, А) - ориентированный граф. Любой орграф можно интерпретировать как частный случай соответствия отображение G = (X,X,Г). В качестве областей отправления и прибытия соответствия в этих случаях всегда выступает множество вершин графа Х. Поэтому само отображение можно заменить при описании графа его графиком Г. Соответствием Г называется отображение множества Х в Х, а граф в этом случае задаётся парой G = (Х, Г).

Для описания ориентированного графа G необходимо задать множество вершин Х = {x₁ ... x_n} и соответствие Г, которое показывает, как между собой вершины связаны, т.е. как отображается множество Х само в себя.

Можно рассматривать действие отображения на отдельные вершины, на некоторую совокупность вершин и все вершины графа. Для описания графа необходимо описать действие отображения на каждую вершину графа Г(х_i). Г(x_i) – это множество таких вершин x_j  Х, для которых в графе G существует дуга (x_i, x_j). Совокупность всех n отображений, где n – порядок графа G, даёт полное представление об этом графе.