Представление графов. Использование водных ресурсов по административным территориям Свердловской области

Лекция №5 ГРАФЫ

Использование водных ресурсов по административным территориям Свердловской области

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

Объемы забора и использования воды по управленческим округам Свердловской области приведены в табл. 26.

Таблица 26

Использование водных ресурсов по управленческим округам Свердловской области, млн м³

Управленческий округ	Год	Общий забор воды	Использовано воды
всего	на производственные нужды	хозяйственно- питьевые	орошение	сельхозводоснабжение
Горнозаводской		373,6	310,6	146,3	163,0	0,302	1,032
	360,9	295,5	140,7	153,7	0,165	0,95
Восточный		89,9	79,5	46,4	27,6	0,290	5,17
	71,2	61,6	34,1	23,7	0,011	3,68
Северный		878,7	713,4	627,3	84,2	0,019	1,83
	505,4	333,4	252,4	79,3	0,012	1,69
Западный		389,0	115,1	48,3	63,0	0,696	2,99
	316,2	109,3	44,6	61,6	0,995	2,12
Южный		145,7	110,3	53,3	54,6	1,12	1,30
	151,8	115,6	60,5	53,7	0,55	0,83
Территории, не входящие в управленческие округа		433,2	364,5	78,9	282,8	0,722	0,809
	398,2	330,7	70,1	257,6	0,918	0,779

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

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

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

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

Ребро (дуга) и любая из его двух вершин называются инцидентными. Степень вершины – это количество инцидентных ей ребер (дуг).

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

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

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

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

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

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

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

а) три цикла:

• 0 – 1 – 3 – 5 – 0,

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

• 1 – 3 – 4 – 1.

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

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

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

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

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

Пример:

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

0 1

1 2

2 3

2 4

3 4

4 0

4 2

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

Например:

#define NMAX 10 /* макс. число вершин */