Представление графов

Графы

Лекция 20. Графы

Граф – это множество вершин и соединяющих их ребер.

На рис. 20.1 приведены примеры графов.

а) неориентированный б) неориентированный в) ориентированный

связный граф несвязный граф граф (орграф)

Рис. 20.1. Примеры графов

В ориентированном графе ребра имеют направление и называются дугами. Если есть дуга v1 –> v2 (от вершины v1 к вершине v2), то вершина v1 называется предшественником вершины v2, а вершина v2 – преемником вершины v1.

Вершины, соединенные ребром или дугой, называют смежными. Ребра (дуги), имеющие общую вершину, также называют смежными. Например, на рис. 20.1.а вершина 1 смежна с вершинами 0, 2, 3, 4, на рис. 20.1.в вершина 4 смежна с 0, 2, 3.

Ребро (дуга) и любая из его двух вершин называются инцидентными. Степень вершины – это количество инцидентных ей ребер (дуг). Например, на рис. 20.1.б вершина 0 имеет степень 2, вершина 1 – степень 3, а вершина 4 – степень 0. На рис. 19.1.в вершина 0 имеет степень 2, вершина 2 – степень 4.

Степень графа – это максимальная степень его вершин. Граф на рис. 20.1.а имеет степень 4.

Ребро (дуга), соединяющее вершину с ней самой, называют петлей.

Путь – это последовательность вершин, в которой каждая вершина соединена ребром или дугой со следующей вершиной. Длина пути равна количеству его ребер (дуг). Например, в графе на рис. 20.1.а между вершинами 0 и 3 есть три пути:

0 – 1 – 3 (длина 2),

0 – 1 – 4 – 3 (длина 3),

0 – 5 – 3 (длина 2).

Замкнутый путь, в котором все ребра (дуги) различны, называют циклом. На рис. 20.1.а три цикла:

0 – 1 – 3 – 5 – 0,

0 – 1 – 4 – 3 – 5 – 0,

1 – 3 – 4 – 1.

У взвешенного графа каждое ребро (дуга) имеет вес – числовую или символьную характеристику. У размеченного графа каждой вершине соответствует некоторая информация – метка.

Примеры графов:

1. Схема алгоритма – размеченный орграф, где вершинами являются блоки алгоритма, а дугами – линии передачи управления.

2. Система дорог – взвешенный размеченный граф, где вершины – города, а ребра – дороги между городами. Вес ребра – длина дороги, метка вершины – название города. Если дороги односторонние, то граф – ориентированный.

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

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

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

Пример для рис. 20.1.в:

5 - число вершин

0 1

1 2

2 3

2 4

3 4

4 0

4 2

Если в таком виде хранить граф в памяти, нужно описать два параллельных массива для хранения смежных вершин.

Дата добавления: 2014-01-04