Начертите полный граф который имеет 7 вершин
Перейти к содержимому

Начертите полный граф который имеет 7 вершин

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

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

История возникновения теории графов

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

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

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

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

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

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

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

Кёнигсбергские мосты в виде графа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

K1 : 0 K2 : 1 K3 : 3 K4 : 6
Complete graph K1 Complete graph K2 Complete graph K3 Complete graph K4
K5 : 10 K6 : 15 K7 : 21 K8 : 28
Complete graph K5 Complete graph K6 Complete graph K7 Complete graph K8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\begin<pmatrix>1 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ \end<pmatrix>» /></p> <p>Граф и его матрица смежности.</p> <p>Матрица смежности элементарно реализуется в большинстве языков программирования, достаточно лишь объявить двумерный массив. Посмотрим, как сделать это на языке Python. В большинстве задач на тему «графы» формат входных данных описан так:</p> <p>Напишем функцию, считывающую граф как матрицу смежности:</p> <h4>Список смежности</h4> <p>Этот способ тоже простой, но он значительно оптимальнее матрицы смежности во многих случаях. Для того, чтобы сохранить в памяти граф, заведём для каждой вершины свой список (для удобства все списки можно хранить в одном массиве), и в эти списки занесём номера вершин, в которые ведут рёбра из данной.</p> <p>Посмотрим, как это пишется на Python с тем же форматом входных данных:</p> <h4>Другие способы</h4> <p>Существуют и другие способы хранения графа в памяти, например, <em>матрица инцидентости</em>, которая удобна при использовании методов линейной алгебры в задачах на графах, или списки рёбер, но практическое применение в задачах обычно находят описанные выше два способа.</p> <h3>Основные задачи теории графов</h3> <h4>Обходы графа</h4> <p>Часто требуется обойти все вершины графа в определённом порядке, например, для проверки его на связность или упорядочения задач при планировании (топологическая сортировка графа). Существует два стандартных метода обхода графа — <em>обход в глубину</em> и <em>обход в ширину</em>.</p> <h5>Обход в глубину (DFS)</h5> <p>Обход в глубину можно описать так: представьте, что вы в лабиринте. Идите всегда прямо, а на всех развилках выбирайте самый левый путь. Упёршись в тупик, возвращайтесь обратно до последней развилки и выбирайте следующий путь слева. Продолжайте, пока не обойдёте весь лабиринт.</p> <p>Обычно алгоритм DFS реализуется с помощью списков смежности и рекурсии. Требуется лишь создать функцию dfs(v) , которая будет просматривать всех соседей вершины v и запускать себя для каждого из них. Единственное, что требуется, кроме этого — список уже посещённых вершин, иначе функция может войти в бесконечный цикл.</p> <p>Напишем функцию dfs на языке Python с использованием списков смежности:</p> <p>Теперь достаточно запустить обход из стартовой вершины. Например, так: dfs(0) .</p> <h5>Обход в ширину (BFS)</h5> <p>Обход в ширину можно наглядно представить себе так: в какой-то стартовой точке лабиринта разливается жидкость, и она начинает равномерно заполнять все его помещения, продвигаясь все дальше. При этом в каждый момент времени все точки края разливающейся воды находятся на одном расстоянии от начала.</p> <p>Этот обход, как и обход DFS, можно применять для поиска путей в графах. Основное его отличие в том, что поиск не уходит сразу далеко от начала, а продвигается вглубь графа постепенно, неким «фронтом».</p> <p>Его реализация немного сложнее, чем DFS. Для этого нам понадобится такая структура данных, как <em>очередь</em>. Очередь, как видно из названия, моделирует обычную очередь в магазине. Обычно это список, в которой можно класть элементы с одной стороны, а забирать — с другой. Обход в ширину хранит в очереди вершины, которые еще предстоит просмотреть.</p> <h4>Поиск кратчайших путей</h4> <p>Очень часто требуется найти кратчайший путь между двумя вершинами во взвешенном графе. Очевидный пример — прокладка маршрута по карте. Для решения этой задачи существует большое количество алгоритмов, в числе которых алгоритм Флойда и алгоритм Дейкстры. Алгоритм Флойда является самым простым, но очень неоптимальным — его сложность $O(n^3)$. Алгоритм Дейкстры быстрее ($O(n^2)$ или $O(n \log n)$, в зависимости от реализации), но имеет некоторые ограничения.</p> <p>Рассмотрим самый простой алгоритм поиска пути — <em>алгоритм Флойда</em>. Его преимущества состоят в том, что он реализуется очень легко, может работать с рёбрами отрицательного веса и одновременно находит кратчайшие пути между всеми парами вершин. Алгоритм Флойда — один из немногих алгоритмов, которые лучше работают с матрицей смежности, чем со списками рёбер. Алгоритм последовательно изменяет матрицу смежности, превращая её в матрицу кратчайших путей — в каждой клетке матрицы остаётся длина (сумма весов) кратчайшего пути между соответствующей парой вершин. Условие работы алгоритма — если между какой-то парой вершинам нет ребра, в исходной матрице смежности в этой клетке должна стоять «бесконечность», обычно это число, заведомо больше весов всех рёбер в данной задаче.</p> <p>Алгоритм устроен так: для каждой вершины графа, пусть её номер будет $k$, просматриваются все пары вершин, пусть это $i$ и $j$. Если сумма текущей известной длины пути из $i$ в $k$ и из $k$ в $j$ меньше, чем из $i$ в $j$, то в клетке, соответствующей пути из $i$ в $j$, запоминаем длину пути через $k$, иначе ничего делать не требуется. Таким образом, алгоритм содержит три вложенных цикла, поэтому его сложность — $O(n^3)$.</p> <p>Посмотрим, как реализовать этот алгоритм на Python:</p> <p>Этот алгоритм легко дорабатывается для случая, когда надо получить не только длины кратчайших путей, но и сами пути. Такую модификацию стоит проделать самостоятельно.</p> <p>Алгоритм Дейкстры будет рассматриваться на зимней очной сессии.</p> <h4>Другие задачи</h4> <p>Другими классическими задачами теории графов являются, например, задача <em>топологической сортировки</em> и задача поиска <em>наименьшего остовного дерева</em>. Алгоритмы для решения этих задач также будут рассматриваться на зимней очной сессии.</p> <h2>Семинар ДООМ. Основные понятия теории графов.</h2> <p>Между планетами введено космическое сообщение по следующим маршрутам: З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?</p> <p><b>РЕШЕНИЕ:</b> Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов,</p> <p>где точками обозначим названия пунктов З, К, П, В и т.д,</p> <p>а отрезками — их соединяющие маршруты. Получается следующий чертеж: (рис.1)</p> <p>Глядя на него можно ответить, что от З до М добраться нельзя.</p> <p><i>Ребята мы решили эту задачу с помощью графов.</i> </p> <p><b>ОПРЕДЕЛЕНИЕ:</b> </p> <p>ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков,</p> <p>прямых или кривых (ребра графов).</p> <p><i>Приведите примеры, где в жизни мы встречаемся с графами?</i> </p> <p>(схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)</p> <p>Графы упрощают решение многих логических задач, экономических, физических и других.</p> <p>Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева,</p> <p><b>Рассмотрим процесс соединения вершин графа ребрами.</b> </p> <p>Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом.</p> <p>Графы, в которых не построены все возможные ребра, называется неполным.</p> <p>Графы, в которых построены все возможные ребра , называется полным.</p> <p>В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа.</p> <p>Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа,</p> <p>исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.</p> <p><b>Сформулируем некоторые закономерности, присущие определенным графам:</b> </p> <p>1) Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.</p> <p>2) Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива для любого графа.</p> <p>3) Если степени всех вершин графа равны, то граф называется однородным.</p> <p>4) Число нечетных вершин любого графа четно.</p> <p>5) Невозможно начертить граф с нечетным числом нечетных вершин.</p> <p>6) Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.</p> <p>7) Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.</p> <p>8) Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.</p> <p><b>Разберем еще некоторые понятия, необходимые для решения задач, используя графы.</b> </p> <p>Путем в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины,</p> <p>что никакое ребро при движении не повторяется дважды.</p> <p><i>Циклом называется путь</i>, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл</p> <p>называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.</p> <p><i>Две вершины графа называются связными</i>, если в графе существует путь с концами в этих вершинах. Если такого пути нет ,</p> <p>то граф несвязный.</p> <p><i>Деревом называется любой связный граф</i> , не имеющий циклов.</p> <p>Для каждой пары вершин дерева существует единственный путь, их соединяющий. (рис.2)</p> <p>Рассмотрим задачу, которую легко можно решить, используя теорию графов.</p> <p>Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки.</p> <p>Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?</p> <p>обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке,</p> <p>пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,</p> <p><i>Для следующей задачи постройте граф, соответствующей решению задачи.</i> </p> <p>В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена.</p> <p>Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.</p> <p>Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой.</p> <p>Сколько пар проведено и сколько еще осталось?</p> <p><b>РЕШЕНИЕ:</b> (рис.6)</p> <p><i><b>ДОМАШНЕЕ ЗАДАНИЕ:</b></i> </p> <p>Решите с помощью графов.</p> <p>ЗАДАЧА: В семье четверо детей, им — 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена.</p> <p>Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три. Сколько лет Лене?</p> <p><i>Ответ: Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет.</i> </p> <p>Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.</p> <h2>Решение простых комбинаторных задач с помощью графов</h2> <p>Кроме таблиц, удобным инструментом для перебора и подсчёта различных комбинаций является граф.</p> <p><b>Граф</b> – это абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.</p> <p><img decoding=

Граф из 6 вершин и 7 ребёр.

Сколько различных трёхзначных чисел можно написать с помощью цифр 0 и 1?

Сколько различных трёхзначных чисел можно написать с помощью цифр 0 и 1?

Получаем 4 числа: 100,101,110 и 111

Полный граф в комбинаторике

Полный граф – это граф со всеми возможными ребрами.

Полный граф

С помощью полного графа удобно решать задачи полного перебора про «всех со всеми».

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

Изобразим полный граф с 5-ю вершинами и посчитаем количество ребёр.

Полный граф с 5-ю вершинами

N = 10. Значит, было сыграно 10 матчей.

Граф-дерево

Дерево – это граф без циклов, у которого между парами вершин имеется только одно ребро.

Граф-дерево с 9 узлами и 8 ребрами.

Граф-дерево с 9 узлами и 8 ребрами.

Из каждого узла выходит не более 2 ребер.

Такое дерево называют бинарным.

С помощью дерева удобно составлять упорядоченные комбинации элементов.

На столе стоит три стакана сока – апельсиновый, виноградный и яблочный. Можно взять только два стакана. Сколько есть возможных вариантов и каких?

По правилу произведения число возможных вариантов: $3 \cdot 2 = 6$. Поскольку, порядок выбора неважен, остаётся $\frac<6> <2>= 3$ варианта. Построим граф:

Упорядоченные комбинации элементов

3 варианта: 1) апельсиновый + яблочный, 2)апельсиновый + виноградный, 3) виноградный + яблочный.

Примеры

Пример 1. Вася, Петя, Коля и Толя хотят быть дежурными в столовой. Но можно выбрать только троих. Сколько вариантов выбора есть?

Построим полный граф.

Пример 1.

Каждая тройка ребят соответствует треугольнику в этом графе.

Например, Вася образует три треугольника с оставшимися тремя ребятами:

$ \frac<3\cdot 2> <2>= 3$ — ВПК, ВТК и ВТП

Без Васи есть только один треугольник – ПКТ

Общее количество треугольников 3+1=4

Ответ: 4 варианта

Пример 2. Под рукой есть 6 видов овощей (капуста, морковь, лук, помидоры, огурцы и перец). Для салата нужно 3 вида овощей. Сколько всего различных салатов можно приготовить?

Построим полный граф.

Пример 2.

Каждые три овоща на полном графе образуют треугольник.

Например, капуста образует треугольники с оставшимися 5 овощами. Таких треугольников $ \frac<5\cdot 4> <2>= 10$, где деление на 2 учитывает повторение ребра в каждой паре («лук-огурец» = «огурец-лук» и т.д.).

Количество треугольников, в которые не входит капуста: $ \frac<4\cdot 3> <2>= 6$

Количество треугольников, в которые не входят капуста и морковь: $ \frac<3\cdot 2> <2>= 3$

Количество треугольников, в которые не входят капуста, морковь и перец: $ \frac<2\cdot 1> <2>= 1$

Итого 10+6+3+1 = 20 различных треугольников.

Ответ: 20 салатов

Примечание: по расчетной формуле $C_6^3 = \frac<6\cdot 5 \cdot 4> <1\cdot 2 \cdot 3>= 20$ — ответ правильный.

Пример 3*. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 11 команд? Решите задачу с помощью полного графа.

Если построить полный граф с 11-ю вершинами, каждая тройка команд в нём образует треугольник.

Пример 3*.

По аналогии с примерами 1 и 2, общее количество треугольников:

Так, как порядок мест важен, в каждом треугольнике $– 3\cdot2 = 6$ вариантов распределения медалей.

По правилу произведения: $6\cdot165 = 990$ — общее количество способов.

Ответ: 990 вариантов

Примечание: по расчетной формуле $A_3^ <11>= 11\cdot10\cdot9 = 990 $ — ответ правильный.

Пример 4. В столовой есть на выбор

  • два первых блюда: щи (Щ) и борщ (Б)
  • три вторых блюда: мясо (М), рыба (Р), блинчики с творогом (Т)
  • два напитка: компот (К) и сок (С)

Сколько вариантов обедов можно составить из этих блюд и каких?

По правилу произведения общее количество вариантов обедов: $2\cdot3\cdot2 = 12$

Похожие публикации:
  1. Как изменить размеры столбца строки в ворде
  2. Как перевести из пдф в ворд для редактирования скачать программу
  3. Какой шрифт использует ютуб
  4. Какую команду надо прописать для закрытия программы

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

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