Сообщение задачи приводящие к понятию граф
Обновлено: 05.07.2024
Цель: показать, как математическая теория графов связана с различными областями деятельности человека, в том числе на железнодорожном транспорте.
1. Освоить основные понятия теории графов.
2. Научиться решать задачи различного рода, посредством графов, в частности использование современных компьютерных технологий для построения графов.
3. Познакомиться с применением графов в железнодорожной отрасли.
Математические графы с дворянским титулом "граф" связывает общее происхождение от лат. слова "графио" - пишу.
Развитие этой задачи привело к циклу задач об обходах графов; задачи о перевозках, решение которых привело к созданию эффективных методов решения транспортных задач. Попытки решить сформулированную в середине 19 века задачу четырех красок, привели к появлению некоторых исследований графов имеющих теоритическое прикладное значение. Изучение Кирхгофом электрических цепей привело к разработке им основных понятий и получению ряда теорем, касающихся деревьев в графах. Другой подход к графам, связанный с рассмотрением головоломок был предложен Гамильтоном. А. Кэли исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и подсчета деревьев, обладающих заданными свойствами, и решил некоторые из них. Учение о цепях Маркова в теории вероятностей связано с ориентированными графами в том смысле, что события представляются вершинами, а ориентированное ребро (дуга), идущее из одной вершины в другую, указывает на то, что вероятность прямого перехода от одного события к другому положительна.
Теоретико-графовый подход используется также в разделах линейного программирования и исследованиях операций при изучении потоков в сетях.
В 20-м веке задачи связанные с графами, начали возникать не только в физике, электротехнике, химии, биологии, экономики, социологии и т.д., но и внутри математики, в таких ее разделах, как алгебра, топология, теория вероятностей, теория чисел и др. Методы этих разделов стали успешно использоваться для решения задач теории графов. Наряду с термином "граф" в начале 20 века употреблялись в качестве синонимов и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт.
Широкое развитие теории графов получило с 50-х годов 20 века в связи со становлением кибернетики и развитием вычислительной техники. Теория графов является частью как топологии, так и комбинаторики.
Основные определения теории графов
Граф G состоит из конечного непустого множества V, содержащего p вершин, и заданного множества X, содержащего q неупорядоченных пар различных вершин из V.
Каждую пару x= вершин в X называют ребром графа G и говорят, что x соединяет u и v. Тогда если дана запись x=uv - это означает, что u и v – смежные вершины, а вершина v и ребро х инцидентны, так же как u и x.
Пример: У графа G на рис.3. вершины u и v смежные, а вершины u и w нет; ребра x и y смежные, а x и z нет. Хотя на рисунке ребра x и z пересекаются, их точка пересечения не является вершиной графа.
Имеется несколько типов графов, которые целесообразно привести.
Отметим, что в графе не может быть петель, т.е. ребер, соединяющих вершины сами с собой. В мультиграфе не допускаются петли, но пары вершин могут соединяться более чем одним ребром. Эти ребра называют кратными. Если допускаются петли и кратные ребра, получаем псевдограф.
Ориентированный граф (или орграф) D состоит из конечного непустого множества V вершин и заданного набора X, упорядоченных пар различных вершин. Элементы X называются ориентированными ребрами (или дугами).
По определению в ориентированном графе нет петель и кратных дуг.
Направленный граф – это орграф, не имеющий симметрических пар ориентированных ребер, т.е. ребер вида (u,v) и (v,u).
Маршрутом в графе G назыается чередующаяся последовательность вершин и ребер v 0 , x 1 , v 1 , … , v n-1 , x n , v n ; эта последовательность начинается и заканчивается вершиной, и каждое ребро последовательности инцидентно двум вершинам одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним. Указанный маршрут соединяет вершины v 0 и vn и его можно обозначить v 0 , v 1 , … , v n (наличие ребер подразумевается).
Маршрут замкнут, если v 0 =v n , и открыт в противоположном случае.
Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины (а следовательно, и ребра) различны. Граф называется связным если все его вершины соединены простой цепью. Максимальный связный подграф графа G называется компонентой связности или компонентой. Замкнутая цепь называется циклом. Замкнутый маршрут называется простым циклом, если все его n вершин различны и n3.
Точкой сочленения графа называется вершина, удаление которой увеличивает число компонент; ребро с такими же свойствами называется мостом. Т.о. если v – точка сочленения связного графа G, то граф G-v не связен. Неразделимым графом называется связный, непустой, не имеющий точк сочленения граф. Блок графа – это его максимальный неразделимый подграф. Если G – неразделимый граф, то часто он сам называется блоком.
Топологические аспекты теории графов были впервые выявлены в 1736 г. Леонардом Эйлером и затем к ним не возвращались в течение 191 года. Интерес к этой теме возобновился после того, как Куратовский нашел критерий, позволяющий определить, является ли граф планарным. Другим пионером в исследовании топологических проблем теории графов был Уитни, полечивший некоторые важные признаки укладки графов на плоскости.
Прежде чем переходить к определениям планарности и укладки считаем необходимым обратиться к очень старой головоломке, которая называется Задача о трех домах и трех колодцах.
Спустя некоторое время обитатели домов А, В и С серьезно поссорились друг с другом и решили проложить дорожки к трем колодцам X, Y, Z так, чтобы по пути к колодцам и обратно им не приходилось встречать друг друга. Задача состоит в том, что могут ли жители этих трех домов проложить дорожки к колодцам указанным образом.
В данном случае дело сводится к тому, чтобы выяснить, можно ли некоторый граф изобразить на плоскости так, чтобы его ребра не имели точек пересечения.
Вопрос, который необходимо поставить, состоит в следующем: является ли соответствующий граф плоским, т. е. можно ли провести его ребра так, чтобы они не пересекались нигде, кроме вершин графа A, B, C, X, Y, Z.
Решить задачу посредством проб и повторных попыток не дает еще математического доказательства того, что это вообще невозможно сделать. Строгое же доказательство основано на теореме Жордана о кривых.
Есть такое понятие как Жорданова кривая (или жорданова дуга) на плоскости называется непрерывная кривая, не имеющая самопересечений. Замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают.
Говорят, что граф G может быть уложен (или обладает укладкой) в данном пространстве, если он изоморфен некоторому графу, изображенному в этом пространстве при помощи точек, представляющих вершины G, и жордановых кривых, представляющих ребра, причем эти кривые не пересекаются друг с другом.
Каждый граф может быть уложен в трехмерном евклидовом пространстве.
То есть, если взять трехмерное представление и спроектировать его на плоскость так, чтобы никакие две вершины не попадали в одну и туже точку, то в некоторых случаях мы получим графы, у которых ребра пересекаются только в точках, являющихся вершинами. Произойдет это только тогда, когда рассматриваемый граф может быть уложен на плоскости; такие графы называются планарными графами.
Плоским графом называется граф, изображенный на плокости так, что никакие два его ребра (или, вернее, пердставляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины. Или, иначе, плоским графом называется граф, который можно начертить на плоскости таким образом, чтобы его ребра не имели точек пересечения, отличных от вершин.
Граф, изоморфный плоскому графу, называется планарным. На языке укладки графов можно сказать, что граф планарен, если его можно уложить на плокости. Граф не является планарным если не существует изоморфного ему графа, начерченного на плоскости, с соблюдением требуемых условий.
Области, определяемые плоским графом, называются его гранями (или внутренними гранями); неограниченную область называют внешней гранью. Если границей грани плоского графа является простой цикл, то иногда под гранью понимают этот цикл.
В курсе школьной геометрии изучается теорема Эйлера о многогранниках .
Переведем ее на язык графов.
Теорема Эйлера (1752 г.). Пусть G – связный плоский граф, пусть n, m и f обозначают соответственно число вершин, ребер и граней графа G. Тогда
Применение графов к решению задач
1. Выяснить, планарны ли графы, изображенные на рисунке
Ответ: Граф G является планарным.
б) Граф Н не планарен
б) М-р Робинсон живет в Лос-Анджелесе.
в) Кондуктор живет в Омахе.
г) М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.
д) Пассажир – однофамилец кондуктора живет в Чикаго.
е) Кондуктор и один из пассажиров, известный специалист по математической физике, ходят в одну церковь.
ж) Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.
Какая фамилия машиниста?
Графы в информатике
Способы представления графов в компьютере:
Конструирование структур данных для представления в программе объектов математической модели – это основа искусства практического программирования. Далее приводится четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.
Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) – объема памяти для каждого представления. Здесь p – число вершин, а q – число ребер.
Компьютеру удобнее всего хранить информацию в виде таблиц (массив тоже можно считать простейшей таблицей). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами.
Матрица смежности имеет m – строк и n – столбцов, где m – количество вершин графа. Элементами матрицы смежности являются 0 и 1, Если вершины соединены, то ставится 1 и если не соединены то 0.
Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая.
Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).
2. Теоретический материал к теме “Графы”.
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.
Рассмотрим две задачи.
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.
Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?
Решение: Занумеруем последовательно клетки доски:
А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:
Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.
Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.
Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:
Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.
Степени вершин и подсчет числа ребер графа
Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.
С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.
Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.
Теорема: Любой граф содержит четное число нечетных вершин.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Связность графа
Есть еще одно важное понятие, относящееся к графам – понятие связности.
Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа.
Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.
Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:
Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.
Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”
Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:
Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:
Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.
Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.
Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?
Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.
Сейчас мы доказали теорему об Эйлеровых графах:
Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.
И в заключение – задача о Кенигсбергских мостах.
Задача 7. На рисунке изображена схема мостов города Кенигсберга.
Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?
3. Задачи к теме “Графы”
Понятие графа.
1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?
Решение. Занумеруем клетки доски, как показано на рисунке:
Каждой клетке поставим в соответствие точку на плоскости и, если из одной клетки можно попасть в другую ходом шахматного коня, то соответствующие точки соединим линией. Исходная и требуемая расстановки коней показаны на рисунках:
При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно.
2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?
Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.
Степени вершин и подсчет числа ребер.
3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.
Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.
4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?
Ответ. Нет (теорема о четности числа нечетных вершин).
5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?
Ответ. Нет, не может.
6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.
7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.
Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.
Связность.
8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.
Доказательство. Рассмотрим компоненту связности, в которую входит один из городов, дорогу между которыми закрыли. По теореме о четности числа нечетных вершин в нее входит и второй город. А значит по-прежнему можно найти маршрут и добраться из одного из этих городов в другой.
Графы Эйлера.
9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист
а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?
10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?
1. Задачи, приводящие к теории графов. Основные понятия и определения.
2. Историческая записка
• Леонард Эйлер (1707-1783)- швейцарец по
происхождению. Приехал в Санкт-Петербург в
1727 году. Не было такой области математики
XVIII века, в которой Эйлер не достиг бы
заметных результатов. Например, решая
головоломки и развлекательные задачи, Эйлер
заложил основы теории графов, ныне широко
используемой во многих приложениях
математики.
• Напряженная работа повлияла на зрение ученого,
в 1766 году он ослеп, но и после этого
продолжал работу, диктуя ученикам свои статьи.
• Эйлер умер в 76 лет и был похоронен на
Смоленском кладбище Санкт-Петербурга. В 1957
году его прах был перенесен в АлександроНевскую лавру.
2
3. Приложения теории графов
- Задача о кратчайшей цепи
составление расписания движения транспортных средств,
размещение пунктов скорой помощи,
размещение телефонных станций.
- Задача о максимальном потоке
анализ пропускной способности коммуникационной сети
организация движения в динамической сети
оптимальный подбор интенсивностей выполнения работ
задача о распределении работ
- Задача об упаковках и покрытиях
оптимизация структуры ПЗУ
размещение диспетчерских пунктов городской транспортной сети
- Раскраска в графах
распределение памяти в ЭВМ
проектирование сетей телевизионного вещания
- Связность графов и сетей
проектирование кратчайшей коммуникационной сети
синтез структурно-надежной сети циркуляционной связи
анализ надежности стохастических сетей связи
- Изоморфизм графов и сетей
структурный синтез линейных избирательных цепей
автоматизация контроля при проектировании БИС
- Изоморфное вхождение и пересечение графов
локализация неисправности с помощью алгоритмов поиска МИПГ
покрытие схемы заданным набором типовых подсхем
- Автоморфизм графов
конструктивное перечисление структурных изомеров для
производных органических соединений
синтез тестов цифровых устройств
3
4. Задачи, приводящие к теории графов
• Попробуйте нарисовать закрытый конверт одним росчерком, т.е.,
не отрывая карандаша от бумаги и не проводя дважды один и тот
же отрезок.
• А если конверт распечатать?
4
5. Задача о Кёнигсбергских мостах
6. Задача о трех домах и трех колодцах
Всегда ли можно изобразить граф на плоскости так, чтобы его ребра не
пересекались? Впервые этот вопрос возник при решении старой
головоломки. Вот как ее описывает Льюис Кэрролл.
В трех домиках жили три человека, неподалеку находилось три колодца:
один с водой, другой с маслом, а третий с повидлом. Однако хозяева
домиков перессорились и решили провести тропинки от своих домиков к
колодцам так, чтобы эти тропинки не пересекались. Первоначальный
вариант по этой причине их не устраивал.
6
Основные понятия и определения
Определение 1
V
Под графом будем понимать пару (V , E ) , где
– произвольное
непустое множество, аE – подмножество множества
V ( 2) ( E V ( 2) )
Если множество V конечно, то граф называется конечным,
иначе – бесконечным.
Элементы множества V называются вершинами графа, а
элементы множества E – ребрами графа.
Вершины графа обозначают точками на плоскости, а ребра
графа – кривыми на плоскости, соединяющими
соответствующие точки. Такие рисунки называют графами.
Множество вершин и ребер графа G обозначают V(G) и E(G)
соответственно.
7
Пример
b
a
g
c
f
e
d
G
V (G ) a, b, c, d , e, f , g , E (G ) (a, b), (a, c), (a, d ), (a, f ), (b, c),
(b, g ), (b, e), (c, e), (d , f ) .
8
Определение 2
a) Если в графе допускается существование повторяющихся
(кратных) ребер, то граф называется мультиграфом.
a) Если в графе, кроме того, допускается существование петель, т.е.
ребер, соединяющих вершину саму с собой, то граф называется
псевдографом.
9
Определение 3
Если мощность множества V равна n , то число n называется
порядком графа.
Определение 4
Если мощность множества V равна n, а мощность множества E
равна m, то граф называется (n,m) - графом.
Определение 5
Две вершины графа называются смежными, если они соединены
ребром.
Определение 6
Два ребра называются смежными, если они выходят из
одной вершины.
11
Определение 7
Ребро и вершина называются инцидентными, если данная
вершина является концом данного ребра.
Определение 8
Окружением вершины v в графе G называется множество смежных
с ней вершин графа G. Обозначают: N (v), N (v) .
G
Вернемся к примеру.
12
Пример
b
a
g
c
f
e
d
G
N ( a ) ? Смежны ли вершины a и b , a и g ?
Смежны ли ребра ( a , b ) и ( a , d ), ( a , b ) и ( c , e ) ?
Являются ли инцидентны ми вершина f и ребро ( f , d ) ?
13
Определение 9
Граф называется пустым, если в нем нет ребер.
n
Обозначают:On илиEn – пустой граф порядка
.
Определение 10
Граф называется полным, если любые две его вершины
соединены ребром.
n
Обозначают: K n илиFn – полный граф порядка
.
Определение 11
Два графа G и H называются равными, если
V(G)=V(H) и E(G)=E(H).
Обозначают: G=H.
14
16. Дополнительные графы. Самодополнительные графы
Дополнительные графы.
Самодополнительные графы.
Определение 1
Пусть дан граф
G
G (V , E ) . Дополнением графа
(или допо лнительным графом G
к
) называется граф G
(V , E V ( 2 ) ) ,
Gв
V (G ) V (G ) и любые две несовпадающие вершины смежны
тогда и только то гда, ко гда они не смежныG
в
.
т.е.
Пример
1
2
3
1
4
G
2
3
4
G
17
Определение 2
Два графа называются изоморфными, если существует перестановка вершин, при
которой графы совпадают. Иначе говоря, два графа называются изоморфными, если
существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое
сохраняет смежность и инцидентность (графы отличаются только названиями своих
вершин).
Обозначают:
G H - G изоморфен H .
Пример
b
3
a
2
c
4
1
5
G1
f
d
G2
G1 G2 , так как существует со храняющая отношение смежности биекция
: V (G1 ) V (G2 ) .
18
(1) b, (2) a, (3) c, (4) f , (5) d .
Определение 3
Граф называется сомодополнительным, если он изоморфен
своему дополнению.
Пример
3
2
2
4
1
5
G
4
5
1
3
G
G G , G -самодополнительный.
19
Теорема 4
1) G G .
2) G
H G H .
3)Для любого
(n, m) - графаG
G
, граф
является
n(n 1)
m - графом.
n,
2
n
4)Если G – самодополнительный граф порядка
n n 1
то G является n,
- графом.
4
,
20
Графом называется пара , где — непустое конечное множество элементов, называемых вершинами , а — конечное семейство неупорядоченных пар элементов из (необязательно различных), называемых ребрами . Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть множеством вершин " , а — семейством ребер графа . О каждом ребре вида " width="56" height="22" />
говорят, что оно соединяет вершины и . Каждая петля " width="52" height="22" />
соединяет вершину саму с собой.
При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; длины отрезков и расположение точек произвольны.
Определение орграфа
называется пара , где — непустое конечное множество элементов, называемых вершинами , а — конечное семейство упорядоченных пар элементов из , называемых дугами (или ориентированными ребрами ). Дуга, у которой вершина является первым элементом, а вершина — вторым, называется дугой из в . Заметим, что дуги и различны. Хотя графы и орграфы — существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги.
Полный граф
.
Граф, не являющийся полным, можно преобразовать в полный с теми же вершинами, добавив недостающие ребра. Вершины графа и ребра, которые добавлены, тоже образуют граф. Такой граф называют дополнением графа и обозначают его .
Дополнением графа называется граф с теми же вершинами, что и граф , и с теми и только теми ребрами, которые необходимо добавить к графу , чтобы получился полный граф.
Является граф полным или нет, это его характеристика в целом.
Полный ориентированный граф
Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром. Если с каждого ребра полного ориентированного графа снять направление, то образуется полный граф с неориентированными ребрами.
Рассмотрим соревнование, в котором каждая из команд играет с каждой из остальных команд по одному разу. Такое соревнование называют круговым турниром или турниром в один круг.
Если каждая встреча непременно должна оканчиваться выигрышем одной из команд, то круговой турнир называют бескомпромиссным. Круговой бескомпромиссный турнир проводится, например, в волейболе и баскетболе.
выражает отношение " победила ".
Двудольный граф
Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества " width="20" height="18" />
и " width="20" height="18" />
, так, что каждое ребро в соединяет какую-нибудь вершину из " width="20" height="18" />
с какой-либо вершиной из " width="20" height="18" />
, тогда называем двудольным графом . Такие графы иногда обозначаю ,V_)" width="78" height="22" />
, если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому: в терминах раскраски его вершин двумя цветами, скажем, красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой — синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из " width="20" height="18" />
соединена с каждой вершиной из " width="20" height="18" />
; если же это так и если при этом граф простой, то он называется полным двудольным графом и обычно обозначается " width="47" height="22" />
, где — число вершин соответственно в " width="20" height="18" />
и " width="20" height="18" />
.
имеет ровно вершин и ребер.
Степень вершины
Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.
; при этом вершины и называются инцидентными этому ребру , а ребро — инцидентным этим вершинам . Аналогично,два различных ребра графа называются смежными, если они имеют, по крайней мере, одну общую вершину. Иначе можно определить степень вершины. Степенью или валентностью вершины графа называется число ребер, инцидентных ; степень вершины будем обозначать через . При вычислении степени вершины будем учитывать петлю в два раза, а не один. Вершина степени называется изолированной вершиной , вершина степени называется висячей , или концевой , вершиной. Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом .
Два графа, " width="23" height="18" />
и " width="23" height="18" />
, называются изоморфными , если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в " width="23" height="18" />
равно числу ребер, соединяющих соответствующие вершины в " width="23" height="18" />
.
Имея даже общие представления о графе, иногда можно судить о степенях его вершин. Так, степень каждой вершины полного графа на единицу меньше числа его вершин. При этом некоторые закономерности, связанные со степенями вершин, присущи не только полным графам.
1. В графе сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный еще двести лет назад Эйлеру, часто называют леммой о рукопожатиях . Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях).
2. Число нечетных вершин любого графа четно.
3. Во всяком графе с вершинами, где , всегда найдутся по меньшей мере две вершины с одинаковыми степенями.
4. Если в графе с вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени , либо в точности одна вершина степени .
Связность графа
Назовем граф связным ,если его нельзя представить в виде объединения двух графов, и несвязным — в противном случае.
Маршрутом в данном графе называется конечная последовательность ребер вида
(обозначаемая также через \to v_ \to v_ \to \ldots \to v_" width="209" height="13" />
). Очевидно следующее свойство маршрута: любые два последовательных ребра либо смежны, либо одинаковы. Но не всякая последовательность ребер, обладающая этим свойством, является маршрутом (в качестве примера рассмотрим звездный граф и возьмем его ребра в произвольном порядке). Каждому маршруту соответствует последовательность вершин , v_ \ldots v_" width="94" height="14" />
. " width="20" height="13" />
называется начальной вершиной , а " width="25" height="13" />
конечной вершиной маршрута. Таким образом, мы будем говорить о маршруте из " width="20" height="13" />
в " width="25" height="13" />
. Заметим, что для любой вершины " width="20" height="13" />
тривиальным маршрутом, вообще не содержащим ребер, является маршрут из " width="20" height="13" />
в " width="20" height="13" />
. Длиной маршрута называется число ребер в нем. Маршрут называется цепью , если все его ребра различны, и простой цепью , если все вершины ,\ldots ,v_" width="83" height="14" />
различны, кроме, может быть, =v_" width="67" height="13" />
. Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом . В частности, любая петля или любая пара кратных ребер образует цикл. Путь (последовательность ребер, ведущая от " width="20" height="13" />
к " width="20" height="13" />
, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза) от вершины " width="20" height="13" />
до вершины " width="20" height="13" />
называется простым, если он не проходит ни через одну из вершин графа более одного раза.
Граф называется связным , если для любых двух его вершин и существует простая цепь из в . Любой граф можно разбить на непересекающиеся связные графы, называемые компонентами ( связности ) графа . Таким образом, несвязный граф имеет, по крайней мере, две компоненты. Две вершины эквивалентны (или связаны , если существует простая цепь из одной в другую.Связный граф состоит из одной компоненты. Граф называется несвязным , если число его компонент больше единицы.
Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень .
Если — связный граф и степень каждой его вершины , тогда — простой цикл.
Из каждой вершины данного графа в любую другую ведет путь. Начнем путь из какой-нибудь вершины е и пройдем по одному из двух ребер, которым принадлежит эта вершина. Попав во вторую вершину, выйдем из нее по второму ребру и так далее. С необходимостью все ребра графа будут пройдены, и мы вернемся в исходную вершину.
Если граф — простой цикл, тогда степень каждой вершины равна двум.
Так как граф — замкнутый простой путь, то из каждой его вершины можно попасть в любую другую, не проходя ни через одну вершину более одного раза. Степень каждой вершины такого графа равна двум.
Покажем, что в простом цикле не может быть вершины, степень которой не равна двум.
Если какая-то вершина в графе имеет степень меньше двух, то она не принадлежит никакому простому циклу.
Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по определению) не может содержать все ребра, которым принадлежит эта вершина.
Задачи, приводящие к графам
Задача 1. Лист бумаги Плюшкин (Н.В.Гоголь "Мертвые души") разрезает на три части. Некоторые из полученных листов он также разрезает на три части. Несколько новых листков он вновь разрезает на три более мелкие части и так далее. Сколько Плюшкин получает листиков бумаги, если разрезает листов?
Решение. Будем считать листы бумаги вершинами графа. При разрезании одного листка на три части число листков увеличивается на два (появляются три новых вместо одного). Если же было разрезано листов, то образовалось листов.
Задача 2. Утверждают, что в одной компании из пяти человек каждый знаком с двумя другими. Возможна ли такая компания?
Решение. Каждого из этой компании будем считать вершиной графа. Двое знакомых соединим ребром. Из рассматриваемой компании нельзя выделить ни "четырехугольник", ни "треугольник", поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию. То есть схема знакомства единственная. Всякую схему, напоминающую многоугольник, принято называть циклом. Древние греки "цикл" называли "колесом".
Задача 3. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.
Решение. Переведем условие задачи на язык графов. Каждому из шахматистов поставим в соответствие вершину графа, соединим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим партию друг с другом. Получим граф с девятью вершинами. Степени его вершин равняются числу партий, сыгравших с соответствующими игроками. Покажем, что во всяком графе с девятью вершинами всегда найдутся хотя бы две вершины одинаковой степени.
Каждая вершина графа с девятью вершинами может иметь степень, равную . Предположим, что существует граф , все вершины которого имеют разную степень, т.е. каждое из чисел последовательности является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина степени , то в нем не найдется вершина со степенью , так как эта вершина должна быть соединена ребрами со всеми остальными вершинами графа, в том числе с . Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени и . Следовательно, найдутся хотя бы две вершины, степени которых равны между собой. Таким образом, доказано, что в любой момент найдутся хотя бы двое, сыгравшие одинаковое число партий.
Вывод. Во всяком графе с вершинами, где , всегда найдутся по меньшей мере две вершины с одинаковыми степенями.
Задача 4. Девять человек проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Нужно доказать, что либо в точности один участник еще не сыграл ни одной партии, либо в точности один сыграл все партии.
Решение. Переведем условие задачи на язык графов. Пусть вершины графа — игроки, а каждое ребро означает, что соответствующие игроки уже сыграли между собой партию. Из условия известно, что в точности две вершины имеют одинаковые степени. Требуется доказать, что в таком графе всегда найдется либо только одна изолированная вершина, либо только одна вершина степени .
В общем случае у графа с девятью вершинами степень каждой вершины может принимать одно из девяти значений: . Но у такого графа степени вершин принимают только восемь разных значений, ибо ровно две вершины имеют одинаковую степень. Следовательно, обязательно либо , либо будет значением степени одной из вершин.
Докажем, что в графах с девятью вершинами, из которых в точности две имеют одинаковую степень, не может быть двух вершин степени или двух вершин степени .
Допустим, что все же найдется граф с девятью вершинами, в котором ровно две вершины изолированные, а все остальные имеют разные степени. Тогда, если не рассматривать эти две изолированные вершины, останется граф с семью вершинами, степени которых не совпадут. Но такого графа не существует (см. задачу 3). Значит, это предположение неверно.
Теперь допустим, что существует граф с девятью вершинами, в котором ровно две вершины имеют степень , а все остальные — несовпадающие степени. Тогда в дополнении данного графа ровно две вершины будут иметь степень , а остальные — попарно различные степени. Этого тоже не может быть (см. задачу 3), то есть и второе предположение неверно.
Следовательно, у графа с девятью вершинами, из которых в точности две имеют одинаковую степень, всегда найдется либо одна изолированная вершина, либо одна вершина степени .
Вернемся к задаче. Как и требовалось доказать, среди рассмотренных девяти игроков либо только один еще не сыграл ни одной партии, либо только один сыграл все партии. При решении этой задачи число можно заменить любым другим натуральным числом .
Вывод. Если в графе с вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени , либо в точности одна вершина степени .
Читайте также: