Основы топологии
Граф – конечное множество точек (вершин), любые две из которых соединены линиями (ребрами). Графы м.б. направленными и ненаправленными. Первая работа, раскрывающая основные положения теории графов (решение задачи о Кёнингсбергских мостах) принадлежит Л.Эйлеру (1736 г.) При решении задачи Л.Эйлер пришел к следующим выводам: 1. Число нечетных вершин (вершин, к которым ведет нечетное число ребер) графа должно быть четно. Не может существовать граф, который бы имел нечетное число нечетных вершин. 2. Если все вершины графа четные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой его вершины и завершить в той же вершине. 3. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком. Топологические отношения на основе теории графов ОСНОВНЫЕ ЭЛЕМЕНТЫ ГРАФА Вершины – элементарные объекты графовой структуры, соединенные отрезками (ребрами). Аналог вершины в ГИС – точка. Ребро - соединение между вершинами графа. В ГИС синонимом термина ребро является сегмент (отрезок). Цепь – непрерывная последовательность ребер графа. Цепь называется простой, если все ее ребра различны, и составной — в противном случае. Если вершины цепи различны, то она называется элементарной. В ГИС синонимом цепи является ломаная (линия). Цикл - замкнутая последовательность ребер графа. Графы бывают двух видов: неориентированные и ориентированные (орграфы). Ориентированный граф – граф, в котором каждому ребру, соединяющим две вершины, придана ориентация относительно этих вершин. Дуга - фундаментальное понятие теории графов; определяется как упорядоченная пара вершин, графически изображается отрезком непрерывной кривой со стрелкой, направленной от вершины v - начала дуги к вершине w – концу дуги.
