На этом шаге мы рассмотрим пути минимального суммарного веса во взвешенном графе, алгоритм Дейкстры, алгоритм Краскала, алгоритм Прима. Задача: найти путь (один из путей) минимальной суммарной длины между двумя заданными вершинами взвешенного графа (орграфа) с неотрицательными весами ребер (дуг). Классическим алгоритмом решения данной задачи является алгоритм Дейкстры. При эффективной реализации временная сложность […]
Архив категории ‘Основные понятия теории графов’
Доказательство корректности волнового алгоритма


На этом шаге мы рассмотрим доказательство корректности волнового алгоритма. Под корректностью алгоритма здесь понимается, что: Алгоритм завершает работу за конечное время; Если решение существует, то алгоритм находит правильное решение. Будем называть итерацией волнового алгоритма очередное выполнение шагов (4)-(7) алгоритма. A. Волновой алгоритм завершает работу за конечное число итераций - это […]
Задача нахождения кратчайших путей


На этом шаге мы рассмотрим задачу нахождения кратчайших путей. Многие задачи либо непосредственно сводятся к нахождению в графах кратчайших путей, либо используют поиск путей на одном из этапов своего решения. Пути с минимальным количеством промежуточных вершин Задача: найти путь между двумя заданными вершинами графа (орграфа), количество промежуточных вершин (и, соответственно, ребер) в […]
Графы с атрибутами


На этом шаге мы рассмотрим графы с атрибутами. Во многих случаях элементам (вершинам и ребрам) графа ставятся в соответствие различные данные - атрибуты (метки). Если в качестве атрибутов используются целые или вещественные числа, то такие графы называют взвешенными. Фактически, взвешенный граф - это функция, определенная на графе. В качестве атрибутов могут выступать и […]
Раскраски графов


На этом шаге мы рассмотрим раскраски графов. Вершинной раскраской (далее - просто раскраской) графа называется отображение множества вершин графа на конечное множество (множество цветов); n-раскраска графа - раскраска с использованием n цветов. Раскраска называется правильной, если никакие две вершины одного цвета не смежны. Очевидно, что для графа без петель всегда существует правильная раскраска […]
Формула Эйлера, основные теоремы


На этом шаге мы рассмотрим формулу Эйлера. Формула Эйлера. Для любой геометрической реализации графа G=(V,E) на плоскости верно: p-q+r=2, где p=|V|, q=|E|, r - число граней (без доказательства). Теорема 2. Если в связном планарном графе нет циклов длины меньше k и k=3, то q<=k(p-2)/(k-2), где p=|V|, q=|E|. Доказательство (не совсем формальное). Пусть граф реализован […]
Планарные графы


На этом шаге мы рассмотрим планарные графы. Сопоставив вершинам графа точки на плоскости или в пространстве, а ребрам - линии, соединяющие точки, соответствующие концам ребра, можно получить диаграмму - визуальное представление данного графа. Очевидно, что для любого графа можно построить бесконечное количество таких диаграмм. Если на некоторой диаграмме среди точек, соответствующих вершинам […]
Цикломатическое число и фундаментальные циклы графа


На этом шаге мы рассмотрим цикломатическое число и фундаментальные циклы графа. Цикломатическим числом графа G=(V,E) с k связными компонентами называется число n(G)=|E|-|V|+k. Фундаментальным циклом графа G=(V,E) с остовным деревом T=(V,E') называется простой цикл, получаемый в результате добавления в T одного из ребер G, не принадлежащего E'. Утверждение 1. Количество фундаментальных циклов графа […]
Деревья


На этом шаге мы рассмотрим деревья. Деревом называется произвольный связный граф без циклов. Лемма 1. Пусть G=(V,E) - связный граф, вершины v1 и v2 которого не смежны. Тогда в графе G'=(V,E+(v1,v2)) существует простой цикл, проходящий через ребро (v1,v2). Доказательство. Т.к. G - связный, в нем существует путь из v2 в v1, а значит, […]
Пути и циклы в графе


На этом шаге мы рассмотрим пути и циклы в графе. Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг - в орграфе) вида v0, (v0,v1), v1, ... , (vn-1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин - простой цепью. […]