Графы и сети.

Граф — это набор узлов (вершин) и связей между ними (ребер).

Сеть – граф, в котором вершины связаны между собой по принципу «многие ко многим»

Как представить информацию о графе в памяти компьютера? Хранить ее в виде рисунка (растрового или векторного) неэффективно, потому что рисунок предназначен для восприятия человеком, а не компьютером. Компьютеру удобнее всего хранить информацию в виде таблиц (массив тоже можно считать простейшей таблицей). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования). Если, например, на пересечении строкиA и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности.

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

Если для каждого ребра указано направление, граф называют ориентированным (или орграфом). Ребра орграфа называют дугами. Его матрица смежности не всегда симметричная. 

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

1. Ответьте на вопросы
2. Вспомните теорию
3. Придумайте свою задачку на тему графы. Требования: не менее 5 вершин. Задачу сформулировать словами. Текст задачи вставить в ответы на вопросы.