Графы задачи на знакомства

Глава 1 Знакомство с графами. Том Карты метро и нейронные сети. Теория графов

графы задачи на знакомства

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

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

Решение этой задачи легко изобразить в виде графа-дерева, похожего на алгоритм. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Кто не сумел созвониться и поэтому не пришёл на встречу?

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

То есть, порядок концов ребра существенен. Такой граф с рёбрами, имеющими направление называется ориентированным графом или орграфом. Итак, в нашем множестве A число 1 меньше числа 2 и числа 3, а число 2 меньше числа 3. Этот факт отображаем рёбрами, имеющими направление, что показывается стрелками. Постоить граф для отображения отношения "делится нацело на" на этом множестве.

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

Такие рёбра называются петлями. В данном случае нет необходимости давать направление петле. Таким образом, в нашем примере три обычных направленных ребра и четыре петли.

Построить граф для отображения отношения "декартово произведение множеств". Как известно из определения декартова произведения множествв нём нет упорядоченных наборов из элементов одного и того же множества.

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

Нет времени вникать в решение? В агентстве по недвижимости работают менеджеры Игорь, Сергей и Пётр. Граф, отображающий данные отношения, будет так же двудольным, так как менеджер не работает с менеджером и объект не работает с объектом. Однако, в отличии от предыдущего примера, граф будет ориентированным. В самом деле, например, Игорь работает с объектом О4, но не объект О4 работает с Игорем. Часто, когда такое свойство отношений очевидно, необходимость давать рёбрам направления может показаться "математической тупостью".

Но всё же, и это вытекает из строгого характера математики, если отношение носит односторонний характер, то давать направления рёбрам. В приложениях отношений эта строгость окупается, например, в программах, предназначенных для планирования, где тоже применяются графы и маршрут по вершинам и рёбрам должен проходить строго в заданном направлении. Итак, получаем следующий ориентированный двудольный граф: И вновь к примерам с числами. Построить граф, реализующий отношение, определяющее все пары чисел a и b из множества C, у которых при делении второго элемента на первый получаем частное, которое является целым числом больше 1.

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

Глава 1 Знакомство с графами

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

То есть, от этого самого содержания при моделировании задачи можно абстрагироваться. Перейдём к примерам, иллюстрирующим это замечательное свойство теории графов. На кусочке шахматной доски размером 3 Х 3 размещены два белых коня и два чёрных коня так, как показано на рисунке ниже. Можно ли переместить коней в состояние, которое изображено на следующем рисунке, не забывая, что две фигуры не могут находиться на одной клетке? В конструируемом графе пары вершин будут связаны отношением "ход коня".

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

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

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

Задача о волке, козе и капусте. На одном берегу реки находятся человек Члодка, волк Вкоза Кз и капуста Кп. В лодке одновременно могут находиться человек и не более одного из перевозимых объектов.

Человек должен перевезти на другой берег все объекты, соблюдая условие: В течение XX века невероятное развитие получила и сама теория графов, и ее многочисленные применения в самых разных областях, начиная с задач планирования и заканчивая социологией, архитектурой, урбанистикой, инженерией, а особенно в информатике и телекоммуникациях. Графы связаны с комбинаторикой, дискретной математикой, топологией, теорией алгоритмов, теорией узлов и другими разделами математики.

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

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

графы задачи на знакомства

Голландский ученый Эдсгер Вибе Дейкстра — заинтересовался компьютерными программами в раннем возрасте и посвятил им всю свою жизнь. Он работал в Голландии, а начиная с года — в Техасском университете в Остине.

Задачи на графах

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

Пол Эрдёш — родился и получил образование в Будапеште. За свою жизнь он написал больше работ и сотрудничал с большим числом соавторов, чем любой другой математик XX столетия.

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

Теория графов: основные понятия и задачи. Графы как структура данных

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

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

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

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

Согласитесь, увидеть это не так-то просто! На рисунках ниже изображены четыре графа — аЬс и d. Граф а является исходным, остальные три — его подграфы. Это означает, что в них были выбраны лишь некоторые ребра и вершины исходного графа. Подграфы позволяют изучать графы по частям.

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

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

Пусть G — помеченный граф с вершинами V0, V1, V2.

графы задачи на знакомства

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

Отношения порядка изображаются с помощью ориентированных графов. Связь теории графов и теории множеств более подробно объясняется в Приложении. Для связных графов имеет смысл определить расстояние между вершинами u и v как минимальное количество ребер, образующих маршрут между u и v.

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

графы задачи на знакомства

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

Область, ограниченная ребрами и не содержащая внутри себя вершин и ребер графа, называется гранью. Подсчитать общее число вершин V и число ребер А несложно. При подсчете числа граней С следует учитывать, что внешняя часть плоскости также образует грань, так как она тоже ограничена циклом из вершин и ребер графа. Таким образом, граф, изображенный на следующем рисунке, имеет 10 вершин, 14 ребер и 6 граней. Графы, в которых любая пара вершин соединена ребром, называются полными.