- •21. Графы, основные понятия теории графов, представление графов.
- •22. Алгоритмы обхода графа: обход в глубину.
- •23. Алгоритмы обхода графа: обход в ширину.
- •24. Деревья, бинарные деревья, дерево двоичного поиска.
- •25. Алгоритмы обхода дерева.
- •26. Обработка исключений, оператор try.
- •27. Обработка исключений, операторы checked, unchecked.
- •28. Генерация собственных исключений
- •29. Работа с файловой системой: классы File и FileInfo.
- •30. Работа с файловой системой: классы Directory и DirectoryInfo.
- •31. Механизм сборки мусора, жизненный цикл объекта, поколения объектов.
- •32. Программирование под Windows, событийно-управляемая модель.
- •33. Архитектура приложений Windows Forms
- •34. Стандартные элементы управления: текстовые поля, кнопки, переключатели.
- •35. Стандартные элементы управления: списки, окна диалога.
- •36. Динамическое создание и удаление элементов управления.
- •37. Обработка событий мыши.
- •39. Делегаты. Определение и использование делегатов.
- •40. События. Событийная модель “publisher/subscribers”
- •38. Обработка событий клавиатуры.
21. Графы, основные понятия теории графов, представление графов.
Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между "началом" и "концом" ребра.
Говоря простым языком, граф - это множество точек (для удобства изображения - на плоскости) и попарно соединяющих их линий (не обязательно прямых.
Ребро е и вершина v называются инцидентными друг другу, если вершина v является одним из концов ребра е.
Любому ребру инцидентно ровно две вершины, а вот вершине может быть инцидентно произвольное количество ребер, это количество и определяет степень вершины.
Две вершины называются смежными, если они являются разными концами одного ребра. Аналогично, два ребра называются смежными, если они инцидентны одной вершине.
Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны.
Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v.
Граф называется связным, если все его вершины взаимно достижимы.
Длина пути - количество ребер, из которых этот путь состоит.
Расстояние между вершинами u и v - это длина кратчайшего пути от u до v.
Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны.
Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами.
В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит).
Если в графе присутствуют и ребра, и дуги, то его называют смешанным.
Степень вершины в орграфе - это не одно число, а пара чисел: первое характеризует количество исходящих из вершины дуг, а второе - количество входящих дуг.
Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги.
Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.
Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути.
Матрица смежности Sm - это квадратная матрица размером NxN (N - количество вершин в графе), заполненная единицами и нулями по следующему правилу:
Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = 1, в противном случае Sm[u,v] = 0.
Задать взвешенный граф при помощи матрицы смежности тоже возможно. Необходимо лишь внести небольшое изменение в определение:
Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = ves(e), в противном случае Sm[u,v] = 0.
Список ребер. Этот способ задания графов наиболее удобен для внешнего представления входных данных. Пусть каждая строка входного файла содержит информацию об одном ребре (дуге):
<номер_начальной_вершины> <номер_конечной_вершины> [<вес_ребра>].
Список смежности. Этот способ задания графов подразумевает, что для каждой вершины будет указан список всех смежных с нею вершин (для орграфа - список вершин, являющихся концами исходящих дуг). Конкретный формат входного файла, содержащего списки смежности, необходимо обговорить отдельно. Например, в нашем случае начальная вершина отделена от списка смежности двоеточием:
<номер_начальной_вершины>: <номера_смежных_вершин>.