Задачи по Python с решениями

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

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