Как решить задачу с помощью графа
Перейти к содержимому

Как решить задачу с помощью графа

  • автор:

Как решить задачу с помощью графа

Теория графов применяется при решении задач из многих предметных областей: математика, биология, информатика

1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе — семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках — проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.

Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ.

Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.

Виды графов:

1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.

2. Неориентированный граф — это граф, в котором нет направления линий.

3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).

Решение задач с помощью графов:

Задача 1.

Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.

Задача 2.

На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Вершины графа — это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Ниже представлен разбор задач.

Задачи, которые можно решить с помощью графов

Теория графов содержит множество алгоритмов, которые были созданы для решения конкретных задач. Типичная область их применения ясна из названия. Рассмотрим основные из них.

Поиск кратчайшего пути

Одной из таких задач является поиск кратчайшего пути.

  • Например алгоритм Дейкстры находит кратчайший путь из одной вершины до другой, если он существует. Стоит отметить, что этот алгоритм не работает с графами, где есть циклы с отрицательным весом дуг.
  • Алгоритм Беллмана — Форда может искать кратчайший путь в графах и с отрицательным весом дуг, но он медленнее, чем алгоритм Дейкстры.
  • Например, Алгоритм поиска A* часто используется в компьютерных играх. Так как в алгоритме А* используется эвристическое правило, он не всегда найдёт самый короткий пусть, но найдёт близкий к самому короткому. Алгоритм поиска A* работает быстрее алгоритма Дейкстры.

Таким образом, алгоритмов поиска кратчайшего пути много и каждый из них обладает своей особенностью. Сервис Graphonline использует алгоритмы Дейкстры и с его помощью можно найти кратчайший путь до вершины и минимальное расстояние до всех остальных вершин.

Поиск максимального потока

Алгоритмы поиска максимального потока находят максимальный поток из источника в сток. С помощью этого алгоритма можно решить задачи максимальной пропускной способности трубопровода или дорожной сети или компьютерной сети.

Сервис Graphonline использует алгоритм Проталкивания Предпотока. Например, если у вас есть граф, где вершины это — города, а вес дуг задаёт пропускную способность дорог между городами (например автомобилей в час), то можно легко посчитать сколько машин может доехать из города А в город N за час.

Поиск минимального остовного дерева

Алгоритм ищет дерево минимального веса в графе, которое бы соединяло все вершины. Этот алгоритм можно применять для дорожной или компьютерной сети, где вы хотите оптимизировать стоимость.

Предположим, имеются 7 компьютеров и разные способы проложить локальную сеть. Используя алгоритм поиска минимального остовного дерева, можно легко посчитать, где стоит проложить кабель, чтобы понадобилось минимальное количество кабеля.

Прикладные задачи, решаемые с помощью Теории Графов

Распределение рабочих

В распоряжении имеются N работников и M различных типов работ. Разные работники могут выполнять разные типы работ. Необходимо распределить работников, чтобы максимальное количество из их было занято.

Для решения строим граф, где соединяем работников с теми работами, которые они могут выполнять. Создаём псевдоисток, который соединяется со всеми работниками и сток, с которым соединены все типы работ. После этого ищем максимальный поток от истока к стоку.

Популярность веб-сайтов

Для составления рейтингов веб-сайтов поисковые системы часто учитывают, на какие сайты больше всего ссылаются другие сайты. Для этого можно составить граф, где каждая дуга определяет ссылку одного сайта на другой. Если размер вершин сделать зависимым от количества входящих дуг, то самые популярные сайты будут самыми большими. Для этой цели Граф Онлайн предлагает алгоритм «Визуализация на основе весов».

Теория 6 рукопожатий

Существует социологическая теория, которая гласит, что два любых человека на Земле разделены не более чем пятью уровнями общих знакомых. Таким образом можно говорить о шести уровнях связей. В графе вершинами является человек, а дугой — факт его знакомства с другим человеком. После этого необходимо найти кратчайший путь от одного человека до другого. Длина пути покажет через сколько рукопожатий знакомы эти два человека.

Рекомендация друзей

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

Самый быстрый способ

Предположим, что что-то можно сделать разными способами. Например, добраться от дома до работы мы можем разными способами: поехать на машине, пойти пешком или воспользоваться самокатом. Все эти действия можно представить в виде графа, где дугами будет являться продолжительность определённых действий. Для поиска самого быстрого способа необходимо найти кратчайший путь между начальной и конечной вершиной.

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)

Теория графов при решении задач

Теория графов — раздел математики и информатики, нашедший широкое применение в современных прикладных задачах. В первую очередь, это задачи поиска маршрута на картах, но её применение не ограничивается навигационными приложениями. Графы возникают там, где между данными существуют какие-либо нелинейные связи. Например, это могут быть компьютеры, соединённые в сеть. Или же это могут быть задачи, которые надо выполнить в каком-то порядке, причём некоторые задачи надо выполнять строго после каких-то других. Существуют алгоритмы, позволяющие вычислить оптимальный порядок выполнения таких задач.

История возникновения теории графов. Леонард Эйлер и задача о Кёнигсберских мостах

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Издавна среди жителей Кёнигсберга (теперь Калининграда) была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

Для того, чтобы решить эту задачу, Эйлер сделал специальные обозначения. Каждую часть суши (остров или берег реки) он обозначил кружком на бумаге, а затем соединил линиями те кружки, между которыми существуют мосты. Такие обозначения подчеркивают, что в этой задаче фактическое расположение, форма, длина и другие свойства объектов не представляют интереса, важны только связи между ними. Такая картинка на бумаге или на экране компьютера называется графом. Кружки — это его вершины, а линии — рёбра. Размышляя над этой и другими картинками из кружков и линий, Эйлер пришел к следующим выводам о графах:

  • Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно всегда быть чётно. То есть, просто не может существовать графа, который имел бы нечётное число нечётных вершин.
  • Если все вершины графа чётные, то его можно начертить не отрывая карандаша от бумаги, при этом начинать можно с любой вершины графа и завершить его в ней же.
  • Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
    (такой граф называют уникурсальным)

Доказательство. Вначале заметим, что если все вершины графа имеют степень не меньше двух, то в нем существует хотя бы один цикл.

Рассмотрим случай, когда все вершины четны. Применим «метод стирания». Выберем некоторую точку и начнем строить путь. Так как степени всех вершин четны, то они не меньше двух. Поэтому, войдя по некоторому ребру в данную точку, мы всегда можем выйти из нее по второму ребру. Будем отмечать пройденные вершины. Так как число вершин конечно, то на каком-то шаге мы перейдем в одну из уже отмеченных вершин и таким образом замкнем цикл. Теперь сотрем этот цикл (естественно, запомнив его где-то) и рассмотрим получившийся граф. Он может оказаться несвязным, но, тем не менее, все его вершины будут иметь четную степень. Применим к этому графу ту же процедуру, и будем это делать до тех пор, пока остается хотя бы один нетривиальный подграф. В результате мы получим несколько циклов, которые не имеют общих ребер, а все вместе образуют исходный граф. Нам остается только склеить эти циклы в один. Возьмем два цикла (…ВАС…) и (…НАМ…), имеющие общую вершину А, разрежем их в этой вершине и склеим по такому правилу: сначала выписываем вершины первого цикла, потом, дойдя до точки А, записываем все вершины второго цикла, а затем продолжаем выписывать оставшиеся вершины первого цикла. Очевидно, что в итоге у нас получится один цикл, который содержит все ребра исходного графа.

Предположим теперь, что в исходном графе ровно две нечетных вершины А и В. Соединим их дополнительных ребром АВ, и получим граф, все вершины которого четны. Построим для него эйлеров цикл по указанному выше алгоритму. Перепишем его так, чтобы вершина А была начальной, а ребро АВ — последним. Удалив из этого цикла ребро АВ получим цикл, начинающийся в А и заканчивающийся в В. Этот путь проходит через все ребра исходного графа.

Предположим теперь, что граф уникурсален. Докажем, что в нем не более двух нечетных вершин. Очевидно, что рисовать такой граф нужно, начиная с нечетной вершины. Причем завершить маршрут нужно в другой нечетной вершине. Если же имеется еще одна нечетная вершина, то она не может быть ни начальной, ни конечной. Поэтому, когда мы в нее заходим, то должны обязательно выйти. Каждый проход через вершину уменьшает число не пройденных ребер, связанных с этой вершиной, ровно на два. В итоге, на каком то шаге в нечетной вершине останется только одно не пройденное ребро, зайдя по которому в вершину мы уже не сможем из нее выйти. Теорема доказана полностью.

Граф кёнигсбергских мостов имел четыре нечётные вершины (т.е. все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Определения теории графов

Граф — конечное множество вершин, природа которых не важна, и конечно множество рёбер, соединяющих между собой какие-либо вершины.

Графы могут быть ориентированными и неориентированными. Если в рамках задачи по рёбрам можно перемещаться в обоих направлениях, то граф называется неориентированным. Если же по каждому ребру можно пройти только в одну сторону, то граф ориентированный. В таком случае рёбра обычно обозначаются стрелками, а не просто линиями.

Пример ориентированного графа

Иногда бывает полезно связать с ребрами графа какие-то числа. Это могут быть длины дорог или плата за проезд, если граф моделирует карту какой-то местности. В таком случае граф называется взвешенным, а сами числа — весами.

Пример: граф с шестью вершинами и семью рёбрами

Граф, в котором каждая пара вершин соединена ребром, называется полным. Обозначение: Kn — граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n-угольник, в котором проведены все диагонали.

Ниже приведены полные графы с числом вершин от 1 до 8 и количества их рёбер.

Степенью вершины называется число ребер, которым принадлежит вершина (число рёбер с концом в данной вершине).

Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.

Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.

Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.

Понятия плоского графа и грани графа применяется при решении задач на «правильное» раскрашивание различных карт.

Путем от вершины A до вершины X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

Циклом называется путь, в котором совпадают начальная и конечная точка (т.е. можно «ходить по циклу» — «ходить по кругу»).

Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.

Длиной пути, проложенного на цикле, называется число ребер этого пути.

Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

Специальным типом графов является дерево. В дереве выделяется особая вершина — корень, которая соединена рёбрами с другими вершинами — своими потомками, которые в свою очередь могут иметь своих потомков. Вершина, не имеющая потомков, называется листом. Наглядный пример дерева — иерархия файлов и папок в файловой системе компьютера или систематика живых организмов

Если не выделять особым образом корень, то дерево — это просто любой связный граф, не имеющий циклов.

Представление графов в памяти

Чтобы решать задачи, связанные с графами, нужно сначала научиться сохранять его в памяти, а ещё лучше — сохранять оптимально. Существует несколько способов сделать это, и для каждой конкретной задачи оптимальным будет свой способ.

Матрица смежности

Самый простой способ сохранить граф в памяти — матрица смежности. Нарисуем таблицу, которая чем-то напоминает таблицу умножения: в первой строчке и в первом столбце будут стоять номера (или любые названия) вершин, а на пересечении столбца и строки будем ставить, например, 1 если между этими вершинами есть ребро и 0 если нет. Кроме 1 и 0 можно ставить, например, вес ребра, а для обозначения отсутствия ребра — просто очень большое число. Какой именно вариант использовать, зависит от каждой конкретной задачи. Также задача определяет, что ставить на диагонали получившейся матрицы.

Граф и его матрица смежности.

Матрица смежности элементарно реализуется в большинстве языков программирования, достаточно лишь объявить двумерный массив.

Другие способы

Существуют и другие способы хранения графа в памяти, например, матрица инцидентости, которая удобна при использовании методов линейной алгебры в задачах на графах, или списки рёбер, но практическое применение в задачах обычно находят описанные выше два способа.

Основные задачи теории графов

Обходы графа

Часто требуется обойти все вершины графа в определённом порядке, например, для проверки его на связность или упорядочения задач при планировании (топологическая сортировка графа). Существует два стандартных метода обхода графа — обход в глубину и обход в ширину.

Обход в глубину (DFS)

Обход в глубину можно описать так: представьте, что вы в лабиринте. Идите всегда прямо, а на всех развилках выбирайте самый левый путь. Упёршись в тупик, возвращайтесь обратно до последней развилки и выбирайте следующий путь слева. Продолжайте, пока не обойдёте весь лабиринт.

Обход в ширину (BFS)

Обход в ширину можно наглядно представить себе так: в какой-то стартовой точке лабиринта разливается жидкость, и она начинает равномерно заполнять все его помещения, продвигаясь все дальше. При этом в каждый момент времени все точки края разливающейся воды находятся на одном расстоянии от начала.

Этот обход, как и обход DFS, можно применять для поиска путей в графах. Основное его отличие в том, что поиск не уходит сразу далеко от начала, а продвигается вглубь графа постепенно, неким «фронтом».

Его реализация немного сложнее, чем DFS. Для этого нам понадобится такая структура данных, как очередь. Очередь, как видно из названия, моделирует обычную очередь в магазине. Обычно это список, в которой можно класть элементы с одной стороны, а забирать — с другой. Обход в ширину хранит в очереди вершины, которые еще предстоит просмотреть.

Другие задачи

Другими классическими задачами теории графов являются, например, задача топологической сортировки и задача поиска наименьшего остовного дерева.

Проблема четырёх красок

Проблема четырёх красок — математическая задача, предложенная Гутри в 1852 году.

Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.

Иначе говоря, показать что хроматическое число плоского графа не превосходит 4.

О доказательстве

К.Аппель и В.Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Исторически планарные графы связаны с одной знаменитой задачей.

Задача о домиках и колодцах. В некоторой деревне есть три колодца. Трое жителей, живущие в трех стоящих рядом домиках перессорились, и решили так протоптать тропинки от своих домов к каждому из трех колодцев, чтобы они не пересекались. Удастся ли им выполнить свой план?

Решим эту задачу. Проведем тропинки так, как это показано на рисунке 8. Как видно, нам удалось провести только восемь тропинок, а девятая должна пересечься хотя бы с одной. Можно доказать (мы не будем приводить строгое доказательство), что эта задача не имеет решения. Дело в том, что по мере проведения тропинок из двух первых домиков, будет получаться некоторый замкнутый контур, внутри которого будет стоять один из колодцев, при этом третий домик будет находиться снаружи от этого контура. Для того чтобы соединить этот домик с колодцем, обязательно потребуется пересечь новой тропинкой одну из уже проложенных.

Задача о четырех красках. На политической карте мира нарисовано несколько государств. Карту нужно раскрасить так, что бы две страны, имеющие общую границу, были покрашены в разные цвета.

В классическом варианте предполагалось, что карту можно раскрасить четырьмя цветами. Покажем, как эта задача связана с графами. Обозначим каждую страну на карте точкой, вершины, отвечающие странам, имеющим общую границу, соединим ребрами. Теперь задачу о раскрашивании можно сформулировать так: раскрасить вершины планарного графа так, чтобы любые две смежные были покрашены в разные цвета. Эта задача может быть решена для графов с малым количеством вершин. Если же число вершин достаточно велико, то гипотеза четырех красок оказывается неверной. (Этот факт установлен с помощью мощных компьютеров.)

Вместе с тем, довольно простыми средствами была доказана теорема о пяти красках.

Теорема. Планарный граф можно раскрасить пятью красками так, что любые смежные вершины будут окрашены в разные цвета.

Еще одна интересная проблема: сколькими способами можно раскрасить граф, если имеется n красок.

Оказывается, что число способов раскрашивания является многочленом от n, коэффициенты этого многочлена можно вычислить с помощью специального алгоритма.

Укажем еще одно обобщение задачи о раскрасках. Известно, что граф без самопересечений располагается на некоторой поверхности (на сфере, на торе, на бутылке Клейна и т.п.), какое минимальное количество красок нужно для его раскрашивания?

Ответ на этот вопрос был получен в разделе математики, называющемся «топологией». Оказалось, что для всех замкнутых двумерных поверхностей (кроме сферы), данное число выражается через Эйлерову характеристику этой поверхности.

Примеры решений задач по теории графов

На этой странице вы найдете готовые примеры по теории графов (разделу дискретной математики). Теория графов берет свое начало еще в 18 веке, когда Эйлер написал свою знаменитую статью о Кёнигсберских мостах (см. решения на алгоритм Эйлера). Сейчас достижения теории графов применяются в строительстве, программировании, электротехнике, социологии, экономике, биохимии, телекоммуникациях и планировании транспортных коммуникаций, психологии и т.д.

Какие виды заданий решаются студентами?

Задачи, решаемые в рамках теории графов, можно условно поделить на несколько групп:

  • Определение графа и его свойства. Задачи на построение графа по заданному числу вершин и ребер, построение матрицы смежности и инцидентности, вычисление основных характеристик графа (связность, простота, эйлеровость, полнота, двудольность, регулярность графа и т.п.). Проверка планарности и изоморфности графов.
  • Действия с графами. Добавление и удаление вершин и ребер, компонент связности, слияние вершин, объединение, пересечение, соединение и декартово произведение графов. Построение дополнение графа.
  • Маршруты, цепи и циклы, контуры. Эйлерова цепь и гамильтонов цикл и проверка графа на выполнение этих свойств.
  • Вычисление характеристик графа. Расстояния: диаметр графа, центр графа, радиус графа. Вычисление цикломатического и хроматического числа.
  • Задачи на графах. Задача о кратчайшем пути (алгоритм Дейкстры, Беллмана, построение дерева путей). Задача на построение минимального остовного дерева (алгоритм Краскала). Задача о максимальном потоке в сети (алгоритм Форда-Фолкерсона). Задача о раскраске графа.
  • Изучение деревьев (специальных видов графов без циклов). Деревья применяются в шифровании, программировании и многих других прикладных областях.

Спасибо за ваши закладки и рекомендации

Задачи по графам с решением онлайн

Задача 1. Постройте граф отношения «x+y ≤7» на множестве М=. Определите его свойства.

Построение графа отношения (pdf, 134 Кб)

Задача 2. Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Постройте дерево кратчайших путей.

Решение по алгоритму Дейкстры (pdf, 196 Кб)

Задача 3. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.

Решение задачи о нахождении максимального потока в сети (pdf, 282 Кб)

Задача 4. Постройте остовное дерево минимального веса, используя алгоритмы Прима и Краскала. С помощью матрицы Кирхгоффа найдите количество (неизоморфных) остовных деревьев, используя пакеты компьютерной математики (например, MathCAD, Mathematica, MatLab).

Решение задачи на построение остовного дерева (pdf, 173 Кб)

Задача 5. Требуется составить структурную матрицу для данного орграфа (или графа) и, методами булевой алгебры, найти все пути $P_$ из вершины $i$ в вершину $j$, затем найти все сечения $S_$ между этими вершинами. В данном задании (чтобы исключить возможные неясности графического рисунка) указываются все ориентированные ребра, причем запись (2–4) означает, что 2 вершина связана с 4-й, а обратной связи нет. Напомним, что для нахождения путей из вершины $i$ в вершину $j$ нужно раскрывать минор структурной матрицы$М_$ (вычеркивать из структурной матрицы строчку с номером $j$ и столбец с номером $i$). Сечения же находятся отрицанием путей (конъюнкция меняется на дизъюнкцию и наоборот).

Задача 6. Для графа $G=(X,U)$ выполнить следующее:
1.1. Построить:
— матрицу смежности,
— матрицу инцидентности.
1.2. Определить степени для всех вершин $$ данного графа.

Задача 7. Найти все кратчайшие пути в орграфе, используя алгоритм Флойда.

Задача 8. Задан $G (X,ГX)$
$X=$,
ГХ:
Гx1=, Гx2=, Гx3=, Гx4=, Гx5=.
Определить хроматическое и цикломатическое число данного графа.

Задача 9. Считая данный граф неориентированным, обозначить его вершины и рёбра разными символами и определить.
3.1. Локальные степени и окружения каждой вершины в виде структуры смежности;
3.2. Построить матрицы инцидентности и смежности;
3.3. Рассмотреть части графа. Привести примеры суграфа, накрывающего суграфа. Показать подграф, состоящий из трёх вершин. Сколько таких подграфов можно найти в данном графе? Показать примеры пересечения и объединения частей графа;
3.4. Привести примеры циклического маршрута, цепи, простой цепи. Попытаться найти Эйлеров цикл;
3.5. Определить центр, диаметр и радиус графа.
Считая граф ориентированным, определить
3.6. Степени вершин
3.7. Матрицы инцидентности и смежности.
3.8. Привести примеры пути, ориентированной цепи, простой цепи, контура, цикла и простого цикла.

Решение теории графов на заказ

Выполняем решение задач, контрольных и практических работ по любым разделам теории графов. Подробное оформление, таблицы, чертежи, пояснение, возможно написание программ на языках программирования (для алгоритмов на графах) или использование специальных программ. Решение экономических задач, связанных с теорией графов.

Стоимость примера от 100 рублей , оформление производится в Word, срок от 2 дней. Также оказываем помощь в сдаче тестов по графам.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *