Определение графа и основные понятия.

Для описания строения различных систем, состоящих из связанных между собой элементов, часто используют графические схемы, изображая элементы точками (кружками, прямоугольниками и т.д.), а связи между ними – линиями или стрелками, соединяющими элементы. При этом получаются диаграммы вроде тех, что показаны на рис. 1.1. На данных диаграммах ни способ изображения элементов, ни форма или длина линий не имеют значения – важно лишь, какие именно пары элементов соединены линиями. Однако, эту же структуру можно представить и без графического изображения, а просто перечислив пары связанных между собой элементов: (1,4), (4,5), (5,3), (3,2), (2,1), (1,3). Таким образом мы получаем два списка: список элементов и список пар элементов. Вместе они составляют то, что математически называют «графом». Граф состоит из двух множеств – множества вершин и множества ребер, причем для каждого ребра указана пара вершин, которые это ребро соединяет.

Рис 1.1 г

Рис 1.1 а

Рис 1.1 в Рис 1.1 б

В листинге 1 приводится пример реализации данного графа (Рис 1.1 в) на языке python с использованием библиотек NetworkX и matplotLib.

Листинг 1.

try:

import matplotlib.pyplot as plt

except:

raise

import networkx as nx

G=nx.cycle_graph(24)

pos=nx.spring_layout(G,iterations=200)

nx.draw(G,pos,node_color=range(24),node_size=800,cmap=plt.cm.Blues)

plt.show() # display

Существует также понятие ориентированный граф или орграф. Это есть граф, ребрам которого присвоено направление. Направленные ребрами именуются также дугами или просто ребрами.

То есть на Рис 1.1 г пара вершин (4, 5) и (5, 4) будет различаться, так как ребро, которое их соединяет, будет иметь направление.

Для ориентированных графов выделяют следующие понятия:

- ребро входит в вершину, если по нему можно двигаться в направлении к этой вершине, и выходит из вершины, если по нему можно двигаться в направлении от этой вершины; - входящая степень вершины - это число входящих в нее ребер; - исходящая (или выходящая) степень вершины - это число выходящих из нее ребер; - путь из вершины A в вершину B - это последовательность ребер и промежуточных вершин, по которым можно дойти из A в B; длина пути определяется, как обычно (число ребер); простой путь - как обычно, путь, в котором вершины (и тем более, ребра) не повторяются; - ориентированный цикл - это замкнутый простой путь в ориентированном графе; - сильно связный ориентированный граф - это ориентированный граф, где из любой вершины в любую есть путь (для каждой пары вершин A и B есть как путь из A в B, так и путь из B в A); - компонента сильной связности - это часть графа, которая сама по себе сильно связна, но ее нельзя расширить так, чтобы она осталась сильно связной; между разными компонентами сильной связности могут быть ребра, но все ребра между двумя разными компонентами направлены в одну и ту же сторону;

- смежные ребра – ребра, которые имеют общую концевую вершину.

Вершины иназываютсяконцевыми вершинами (или просто концами) ребра .

По отношению к вершинам ребро e в таком случае называется инцидентным и наоборот.

Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

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

Также, ребро, соединяющее вершину с собой, то есть ребро, которое выходит и входит в одну и ту же вершину называют петлей.

Комбинируя вышеперечисленного можно получить разные варианты определения понятия графа. Чаще всего встречаются графы неориентированные графы без петель и кратных ребер. Такие графы называются обыкновенным графом.

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

            Сам граф по отношению к своим подграфам называется надграфом (суграфом или суперграфом). На Рис. 1.2 представлен подграф графа, приведенного выше (Рис. 1.1 г).

Рис. 1.2

Существует также понятие пустой граф, граф, который не имеет ребер и вершин.

Полным называется граф, в котором две вершины смежны.