Лекция №5 ГРАФЫ
Использование водных ресурсов по административным территориям Свердловской области
Административные территории области (районы, районные центры, отдельные муниципальные образования) сгруппированы по бассейнам рек, в которых они расположены. Степень использования водных ресурсов определяется количеством проживающего в регионах населения, развитием различных по водоемкости отраслей промышленности, сельского хозяйства.
Объемы забора и использования воды по управленческим округам Свердловской области приведены в табл. 26.
Таблица 26
Использование водных ресурсов по управленческим округам Свердловской области, млн м3
Управленческий округ | Год | Общий забор воды | Использовано воды | ||||
всего | на производственные нужды | хозяйственно- питьевые | орошение | сельхозводоснабжение | |||
Горнозаводской | 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 /* макс. число вершин */
#define RMAX 100 /* макс. число ребер */
int v1 [RMAX]; /* массивы смежных */
int v2 [RMAX]; /* вершин */
int n; /* число вершин графа */
int r; /* число ребер графа */
2. Матрица смежности – это квадратная матрица размерности n*n (n – число вершин), в которой элемент
1, если есть дуга i –> j,
ms[i][j] =
0 в противном случае.
Пример матрицы смежности для орграфа, представленного на следующем рисунке:
| 0 1 2 3 4
-----------------