Архив категории ‘Основные понятия теории графов’

Пути минимального суммарного веса во взвешенном графе

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

Доказательство корректности волнового алгоритма

    На этом шаге мы рассмотрим доказательство корректности волнового алгоритма.     Под корректностью алгоритма здесь понимается, что: Алгоритм завершает работу за конечное время; Если решение существует, то алгоритм находит правильное решение.     Будем называть итерацией волнового алгоритма очередное выполнение шагов (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 называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин - простой цепью. […]