"Теория графов"

Автор: Истапаева Елизавета Шараниевна
Должность: учитель математики
Учебное заведение: МБОУ "СОШ №16"г.Грозного
Населённый пункт: Грозный
Наименование материала: статья
Тема: "Теория графов"
Дата публикации: 21.08.2016







Вернуться назад       Перейти в раздел





Текстовая часть публикации

Тезис выступления Тема моего доклада: «Применение графов в задачах о маршрутах» Мы живем во время больших изменений: вводится газовые магистрали, железные дороги, крупные автомагистрали, начаты работы по строительству нефтяных и газовых трубопроводов, планируется строительство моста через реку Лена. Наше село Бедимя расположено в центральной части территории улуса, через территорию которого проходят республиканская дорога Тюнгюлю – Майя, трассы высоковольтных ЛЭП, беспроводная радиолинейная телефонная связь и газопровод. Как показывают наши наблюдения, в нашем селе произошли в последнее время немало интересных событий. К нам приезжал Президент республики В.А.Штыров, который посетил нашу школу, провел совещание с главами крестьянских хозяйств, побывал в крестьянской усадьбе. Много гостей побывало в этом году на республиканском ысыахе. Были у нас гости из ФРГ, Китая, ознакомились с нашими традиционными видами хозяйствования, посмотрели природу нашего края. Данная работа посвящена применению графов в изучении местности родного края. Теория графов – это необычная геометрия без углов и расстояний. Она зародилась двести с лишним лет назад при решении головоломок. Слово «графо» с греческого означает «пишу», с которого образованы слова график, биография. Основы теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о кёнингсбергских мостах. В 2007 году Эйлеру исполнилось 300 лет. Целью исследования является нахождение применения теории графов в решении задач, связанных с окружающей местностью. Для этого нами изучена математическая литература, решены задачи о маршрутах и разработаны задачи об экскурсионных маршрутах на примере местности села Бедимя. Основным источником знаний в теории графов нами взято пособие Ларисы Юрьевны Березиной «Графы и их применение», выпущенное в 1979 году. Использованы книги авторов: Гусев В.А. и др., Нагибин Ф.Ф., Глейзер Г.И., а также Энциклопедия для детей Аванта+. Использован из Интернета спутниковый фотоснимок рельефа нашего села. 1. Поиск различных способов решения олимпиадных задач. 2. Изучение теории графов, решение задач о маршрутах. 3. Приложение графов для разработки практических задач. 4. Защита темы на школьном этапе. Актуальность работы состоит в том, что с помощью графов можно изучать свою местность и окружающую среду. Работа состоит из 4 пунктов: В 1 пункте даются определение и изображение графов. Во 2 пункте изучается знаменитая задача о кёнингсбергских мостах.
В 3 пункте даются решения трех задач. Первые две о маршруте автотуристов, третья о строительстве железной дороги. В 4 пункте показаны две задачи. Первая о построении связного графа с четырьмя вершинами, каждое ребро которого мосты и мелководные участки речек. Ситуация взята из примера нашей местности – долины трех речек: Суола, Тиэрэ, Куелэ. Без мостов мы можем быть отрезанными от большой земли. Железобетонный мост через речку Суола построен в 1981 году, мост через р. Тиэрэ отремонтирован в 2007 году, а строительство моста через р.Куелэ стало долгостроем и надеемся завершится в 2008 году. Вторая задача связана с экскурсионным маршрутом, где достопримечательности села: старая мельница, ипподром, конюшня скакунов, искусственное озеро Лама, музей народной мудрости, крестьянская усадьба, усадьба умельца, природный участок Хороннох, куда дети любят ходить на экскурсии. Нужно составить маршрут, чтобы туристы в каждый из указанных пунктов, попадали не более одного раза. В результате проведенного исследования получены выводы: 1) Графы имеют практическое применение в жизни, особенно в схемах дорог, маршрутов 2) Графы придают условиям задач наглядность, упрощают решение задачи, помогают выявлять сходство задач. 3) С помощью графов можно изучать местность родного села. 4) Из литературы мы узнали, что сейчас почти в любой отрасли науки и техники встречаешься с графами: в электротехнике – при построении электрических схем, в химии и биологии – при изучении молекул и их цепочек, в экономике – при решении задач в выборе оптимального пути для потоков грузового транспорта и во многих других задачах. 5) Изучение графов может помочь нам ещё глубже понять суть математических знаний.
ВВЕДЕНИЕ.
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего. Теория графов является частью как топологии, так и комбинаторики. То, что это топологическая теория, следует из независимости свойств графа от расположения вершин и вида соединяющих их линий. А удобство формулировок комбинаторных задач в терминах графов привела к тому, что теория графов стала одним из мощнейших аппаратов комбинаторики.
ПОНЯТИЕ О ГРАФАХ Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог (рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами. Использует графы и дворянство. На рисунке 2 приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками.
Не трудно понять, что граф – дерево всегда можно изобразить так, чтобы его ребра не пересекались. Тем же свойством обладают графы, образованные вершинами и ребрами выпуклых многогранников. На рисунке 3 приведены графы, соответствующие пяти правильным многогранникам. В графе соответствующем тетраэдру, все четыре вершины попарно соединены ребрами. Рассмотрим граф с пятью вершинами, попарно соединенными друг с другом (рис. 4). Здесь ребра графа пересекаются. Невозможно его изобразить так, чтобы пересечений не было, как невозможно выполнить намерения трех человек, описанных Льюсом Кэрроллом. Они жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке 5. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. На рисунке 6 изображена очередная попытка проложить такие тропы.
Графы, изображенные на рисунках 4 и 5, как оказалось, играют решающую роль при определение для каждого графа – является ли он плоским, то есть может ли он быть изображен на плоскости без пересечения его ребер. Польский математик Г. Куратовский и академик Л. С. Понтрягин независимо доказали, что если граф не является плоским, то в нем «сидит» хотя бы один из графов, изображенных на рисунках 4 и 5, то есть «полный пятивершинник» или граф «домики – колодцы». Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего. Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным. Стрелка от одой работы к другой на графе, изображенном на рис. 7, означает последовательность выполнения работ. Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду и т. д. Около вершин графа указаны числа – продолжительность в днях соответствующей работы . Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 2 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней. На рис.8 изображена схема дорог между селами М, А, Б, В, Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развезти письма по остальным четырем селам. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет
новый граф(внизу), на котором легко увидеть возможные маршруты. Вершина М вверху – начало маршрутов. Из нее можно начать движение четырьмя различными способами: вА, в Б, в В, в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4 3 2 1 = 24 способа. Расставим вдоль ребер графа цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28км, соответствующие маршрутам М-В-Б-А- Г-М и М-Г-А-Б-В-М. Это один и тот же путь, но пройденный в разных направлениях Заметим, что граф на рис. 8 тоже можно сделать направленным, указав направление сверху вниз на каждом из ребер, что соответствовало бы направлению движения почтальона. Подобные задачи часто возникают при нахождении лучших вариантов развозки товаров по магазинам, стройматериалов по стройкам. Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю. Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел ( 8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: ( 3, 5, 0),если наполним водой большую кастрюлю, или ( 5, 0, 3), если наполним меньшую кастрюлю. В результате получаем два решения: одно в 7 ходов, другое в 8 ходов. Подобным образом можно ставить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов», где позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки. Однако для шахмат и шашек такой граф будит очень большим, поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры «крестики – нолики» на доске 3 * 3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков ( но не миллионов) вершин. Свойство графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук – топологии. Впервые основы теории графов появились в работе Л. Эйлера, где он описывал решение головоломок и математических развлекательных задач. Широкое развитие теория графов получила с 50-х гг. 20 в. в связи со становлением кибернетики и развитием вычислительной техники. В терминах графов легко формулируется и решается задача о назначении на должности. А именно: если имеется несколько вакантных должностей и группа лиц, желающих их занять, причем каждый из претендентов имеет квалификацию для нескольких должностей, то при каких условиях каждый из претендентов сможет получить работу по одной из своих специальностей?
Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями. Это дает возможность изучения их свойств с помощью одной из молодых наук – топологии, хотя сами задачи теории графов являются типичными задачами комбинаторики. Вот несколько задач теории графов. Задача об эйлеровом пути: найти путь по ребрам графа, проходящий по каждому ребру ровно один раз. Такой путь существует лишь в том случае, если граф – связный, т. е. от каждой его вершины к каждой другой можно пройти по ребрам графа, и из каждой вершины, кроме, может быть, двух, выходит четное число ребер. На графе, изображенном на рис. 3,а, он есть, а на рис. 3,б его нет. Хроматическим числом графа называется наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединенные ребром, окрашиваются при этом в разные цвета. Долгое время математики не могли решить эту проблему: достаточно ли четырех красок, для того чтобы раскрасить произвольную графическую карту так, чтобы любые две стороны, имеющие общую границу, были окрашены разными красками? Если изобразить страны точками – вершинами графа, соединив ребрами те вершины, для которых соответствующие им страны граничат , то задача сведется к следующей: верно ли, что хроматическое число любого графа, расположенного на плоскости, не больше четырех? Положительный ответ на этот вопрос был лишь недавно получен с помощью ЭВМ. Используя графы можно решать задачи. Вот, например, как выглядит последняя американская версия известной задачи Дьюдени: 1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями. В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р) 2. М-р Робинсон живет в Лос-Анджелесе. 3. Кондуктор живет в Омахе. 4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже. 5. Пассажир – однофамилец кондуктора живет в Чикаго. 6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь. 7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд. Как фамилия машиниста?
Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы). Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.
ЗАКЛЮЧЕНИЕ
В настоящем реферате рассмотрены математические графы, области их применения, решено несколько задач с помощью графов. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты). Кроме того, работая над рефератом, я освоил работу на компьютере в текстовом редакторе WORD. Таким образом, задачи реферата выполнены. Список литературы 1. Энциклопедический словарь юного математикаСост.А.П.Савин.- М.: Педагогика, 1989 2. Квант №6 1994г. 3. М.Гарднер «Математические досуги»М.: Мир, 1972

п.8. Деревья. Остовные деревья.

8.1. Деревья.
Существует один простой и важный тип графов, которому разные авторы дали одинаковое название – деревья. Для них выполняются многие интересные утверждения, которые не всегда выполняются для графов в общем случае. Деревья являются самым распространенным классом графов, применяемых в программировании, причем в самых разных ситуациях.
Определение 8.1. Деревом
называется граф T(V, E) без циклов.
Лес
– это граф, компоненты которого являются деревьями.
Ориентированное дерево T
� представляет собой свободный от петель ориентированный граф, соотнесенный граф которого является деревом. Если дерево имеет хотя бы одно ребро, оно имеет хотя бы две вершины со степенью 1. Вершины степени 1 называются
листьями
. Другие вершины называются
внутренними

вершинами
. Если дерево изображено таким образом, что в верхней части помещена вершина, а остальные находятся ниже его, то вершина в самой верхней части называется
корнем
дерева. Если корень дерева определен, то дерево называется
корневым деревом
. Если корень выбран,
уровень вершины v
определяется длиной единственной цепи из корня в вершину v.
Определение 8.2. Высотой
дерева называется длина самой длинной цепи от корня до листа. Высоту дерева будем обозначать h(T).
Пример 8.1.


Примеры изображения деревьев в программировании.
Тот факт, что большинство систем управления файлами использует ориентированные
Генеалогическое дерево семейства Бернулли.
Купеческая протестантская семья Бернулли жила в Антверпене (Нидерланды). Свой род она вела из Фландрии, где Бернулли, в XV в. носили еще фамилию Бернуйла (Bernuilla). В
связи с событиями XVI в. на территории Нидерландов, что направленные были против протестантов, семья Бернулли была вынуждена уехать во Франкфурт-на-Майне. В это время главой семьи был Якоб Бернулли, который умер в 1583 г. Среди Бернулли некоторые имена повторялись из поколения в поколение, поэтому их различают, как королей, присоединив к имени соответствующую цифру. В виде дерева показана родословная семейства Бернулли. Якоб I (1654-1705) – швейцарский математик. По образованию богослов. С 1687 г. профессор математики Базельского университета. Ему принадлежат важные заслуги в развитии анализа бесконечно малых, начало которому положила работа Лейбница, опубликованная в 1684 г. Он вычислил площади многих плоских фигур, площади поверхностей и длины линий. Другие работы относятся к алгебре, арифметике, геометрии, теории рядов, теории вероятностей, а также к физике. В книге «Искусство предположений» доказал теорему (названную позже его именем), имеющую важное значение в теории вероятностей и ее приложениях к статистике. Учениками Якоба I были: его младший брат Иоганн I, племянник Николай I, член Петербургской академии наук,
механик и математик Я. Герман, отец великого Л. Эйлера — Пауль Эйлер. Иоганн I (1667-1748). Брат Якоба I. Десятый ребенок в семье Николая. По образованию врач. С 1695 г. профессор математики Гронингенского университета (Голландия). С 1705 г. профессор математики Базельского университета. Почетный член Петербургской академии наук. Николай I (1687-1759) – швейцарский математик, сын Николая. По образованию юрист. Был профессором математики в Падуе, а затем профессором логики и права в Базельском университете. Его исследования посвящены теории вероятностей, интегральному исчислению, демографии. Николай II (1695-1726), сын Иоганна I. По образованию юрист. Профессор права в Берне, профессор математики в Петербурге. Даниил I (1700-1782). Уроженец Гронингена, сын Иоганна I. По образованию врач. В 1725- 1733 гг. работал на кафедрах физиологии и механики в Петербургской академии наук. С 1733 г. профессор по кафедре физиологии, с 1750 г. профессор по кафедре механики в Базеле. Почетный член Петербургской академии наук. В математике Даниилу Бернулли принадлежат: метод численного решения алгебраических уравнений с помощью возвратных рядов, работы по обыкновенным дифференциальным уравнениям, по теории вероятностей с приложением к статистике народонаселения и отчасти у астрономии, по теории рядов. В работах, завершенных написанным в Петербурге трудом «Гидродинамика» (1738), вывел основное уравнение стационарного движения идеальной жидкости, носящее его имя. Разрабатывал кинематические представления о газах. Иоганн II (1710-1790), сын Иоганна I. По образованию юрист. Профессор элоквенции (красноречия), профессор математики в Базеле. Иоганн III (1744-1807), старший сын Иоганна II. По образованию юрист. Астроном Берлинской академии наук, там же директор математического класса. Даниил II (1751-1834), второй сын Иоганна II. По образованию врач, профессор красноречия в Базеле. Якоб II (1759-1789), третий сын Иоганна II. По образованию юрист. Математик Петербургской академии наук. Кристоф (1782-1863), сын Даниила II. Профессор технологии в Базеле. Иоганн-Густав (1811-1863), сын Кристофа. Профессор технологии в Базеле. Представители рода Бернулли живут в Базеле и в настоящее время.
Рассмотрим некоторые утверждения, которые относятся к деревьям.
Теорема 8.1.
Для любых вершин a и b дерева T существует единственная цепь из a в b.
Доказательство.
Доказательство проведем методом «от противного». Предпо-ложим, что для некоторых вершин a и b дерева T цепь из a и b не является единственной, и покажем, что в таком случае T не будет деревом. На основании следующей теоремы можно убедиться в том, что верна также и обратная теорема, которую мы примем без доказательства.
Теорема 8.2.
Если для любых двух вершин графа G существует единственная цепь из вершины a в вершину b, тогда G является деревом.
Теорема 8.3.
Если у дерева T имеется e ребер и v вершин, то v=e+1.
Доказательство.
Предположим, что имеется дерево T. Любое дерево можно представить как корневое дерево, и это никаким образом не меняет ни числа ребер, ни числа вершин. Рассмотрим теперь ориентированное дерево T  , порожденное деревом T. У каждой дуги ориентированного дерева одна и только одна конечная вершина. Следовательно, число дуг и вершин одно и то же, исключая корневую. Если учесть корневую вершину, получим, что вершин на одну больше, чем дуг.
Значит, и исходное дерево имеет число вершин на одну больше, чем число ребер. ■ Справедлива также и обратная теорема, которую примем без доказательства.
Теорема 8.4.
Если в связном графе G, содержащем e ребер и v вершин и имеем v=e+1, то G является деревом.
^ 8.2. Остовные деревья.
В этой части лекции мы рассмотрим так называемые остовные деревья и их применение для решения некоторого класса прикладных задач. Сначала дадим определение остовного дерева.
Определение 8.3.
Дерево T называется
остовным деревом
графа G, если T – подграф графа G и каждая вершина G является вершиной в T. Теперь сформулируем теорему, которую примем без доказательства.
Теорема 8.5.
У каждого связного графа существует подграф, который является остовным деревом. Для построения остовных деревьев существуют разные методы. Самыми распространенными являются два метода: метод поиска в ширину и метод поиска в глубину. Согласно методу поиска остовного дерева в ширину произвольную вершину v 0 графа G выбираем в качестве корня дерева T. Для каждой вершины v графа G, смежной с вершиной v 0 , в дерево T добавляется вершина v и ребро (v 0 , v). Это вершины уровня 1. Затем берем каждую вершину v i уровня 1 и для каждой вершины v j графа G, смежной с вершиной v i из тех, что еще не выбраны, добавляем в дерево T вершину v j и ребро (v i , v j ). Вершины, добавленные на этом этапе, - это вершины уровня 2. Продолжаем процесс, пока в графе G не останется вершин, которые можно было бы добавить в дерево. По построению T является деревом. Если расстояние от v 0 до вершины v графа G равно n, то эта вершина будет добавлена в дерево на уровне n. Следовательно, T несомненно, является остовным деревом.
При поиске в ширину первым делом отыскиваются все вершины, смежные с заданной вершиной, а потом осуществляется переход на следующий уровень. При поиске в глубину усилия направлены на построение для дерева как можно более длинного пути. Метод поиска в глубину начинается с задания вершины графа, которую будем считать корнем. Выбираем вершину v i , смежную с корнем, и формируем ребро дерева. Затем выбираем вершину v j , смежную с ранее выбранной вершиной v i , и формируем новое ребро. По ходу необходимо помечать использованные вершины, с тем, чтобы каждая вершина использовалась один раз. Если, находясь в вершине v, мы выбираем другую вершину w и обнаруживаем, что вершина w уже была добавлена в дерево, то ребро (v, w) между этими вершинами не может быть добавлено в дерево. Когда имеем исходный граф, то само собой возникает вопрос: сколько можно построить остовных деревьев для помеченного графа с n вершинами? Ответ на этот вопрос дает теорема Кэли, которая рассматривает число остовных деревьев для K n .
^ Теорема 8.6. (Теорема Кэли)
Число остовных деревьев для K n , у которого вершины помечены, равно . Если рассматривать определенный граф, который отличается от полного, то эта формула не годится для определения числа остовных графов. В этом случае используют теорему Кирхгофа. Прежде чем сформулировать теорему, сначала введем понятие матрица Кирхгофа.
Определение 8.4. Матрицей Кирхгофа
связного графа G с помеченными вершинами называется матрица K v  v =K(G), , которую можно определить следующим образом: .
Теорема 8.7. (Теорема Кирхгофа)
Число остовных деревьев в связном графе G порядка n  2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K(G).
Пример 8.2.
Найти число остовных деревьев данного графа.

Решение.
Сначала составляем для данного графа матрицу Кирхгофа. . Теперь находим алгебраическое дополнение, например, для элемента k 11 матрицы Кирхгофа. . Проверим, например, для элемента k 23 . . Итак, получаем, что данный граф имеет 8 остовных деревьев. 
^ 8.3. Алгоритм Краскала и алгоритм Прима.
В предыдущей лекции мы ввели понятие взвешенного графа, как графа, каждому ребру
которого приписано положительное число, называемое весом. Этот вес может описывать расстояние, стоимость или другие данные.
Определение 8.5. Вес
остовного дерева взвешенного графа G равен сумме весов, приписанных ребрам остовного дерева. Будем обозначать  (T).
Минимальным остовным деревом
называется такое остовное дерево графа G, что вес T меньше или равен весу любого другого остовного дерева графа G. Вес минимального остовного дерева будем обозначать  min (T). Построение остова графа G, имеющего наименьший вес, имеет широкое применение при решении некоторого класса задач прикладного характера. Дадим формулировку одной из таких задач.
^ Формулировка задачи:
Пусть, например, G=(V, E,  ) служит моделью железнодорожной сети, соединяющей пункты v 1 , v 2 , …, v n  V, а  (v i , v j ) – расстояние между пунктами v i и v j . Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все пункты v 1 , v 2 , …, v n были связаны между собой телеграфной сетью, протяженность которой была бы наименьшей. Мы рассмотрим два способа построения минимального остовного дерева взве-шенного графа: алгоритм Краскала и алгоритм Прима. Первым рассмотрим алгоритм Краскала. Идея метода состоит в том, чтобы формировать дерево T(V, E), выбирая ребра с наименьшим весом так, чтобы не возникал цикл.
Алгоритм Краскала:
1) Выбрать в графе G ребро e минимального веса, не принадлежащее множеству E и такое, что его добавление в E не создает цикл в дереве T. 2) Добавить это ребро во множество ребер E. 3) Продолжить, пока имеются ребра, обладающие указанными свойствами. Вторым рассмотрим алгоритм Прима. Принципиальное отличие алгоритма состоит в том, что всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остовное дерево.

Алгоритм Прима:
1) Выбрать вершину v 0 графа G и ребро с наименьшим весом e 1 , для которого v 0 – одна из вершин, и сформировать дерево T 1 . 2) Для заданного дерева T k с ребрами e 1 , e 2 , e 3 , …, e k , если имеется вершина, не принадлежащая T k , выбрать ребро с наименьшим весом, смежное с ребром дерева T k и имеющее вершину вне дерева T k . Добавить в дерево T k , формируя дерево T k+1 . 3) Продолжить, пока имеются вершины графа G, не принадлежащие дереву. Построение минимального оствного дерева можно проводить двумя способами: 1) остов графа строится непосредственно на самом графе, выделяя ребра утолщенной линией, которые входят в остовное дерево; 2) строится отдельно корневое дерево, которое будет минимальным остовным деревом. Второй случай используется, если требуется определить высоту построенного дерева.
Пример 8.3.
Для данного взвешенного графа: 1) определить степень каждой вершины; 2) построить матрицу смежности вершин, матрицу смежности ребер, матрицу инциденций; 3) найти число остовных деревьев, используя теорему Кирхгофа; 4) найти минимальное корневое остовное дерево, используя алгоритм Краскала или алгоритм Прима. Определить высоту построенного дерева.
Решение.
1) Используя определение степени вершины графа, находим: d(v 1 )=3, d(v 2 )=3, d(v 3 )=4, d(v 4 )=3, d(v 5 )=2, d(v 6 )=3. 2) Построим матрицу смежности вершин. Данный граф имеет шесть вершин, поэтому матрица смежности вершин является квадратной матрицей шестого порядка. Для заполнения первой строки матрицы найдем число ребер, соединяющих первую
вершину с каждой из остальных вершин. Поскольку количество ребер, соединяющих первую вершину с первой равно 0 (в графе нет петель, соответствующих первой вершине), соединяющих первую со второй равно 1, первую с третьей равно 1, первую с четвертой равно 1, первую с пятой равно 0, первую с шестой равно 0, то первая строка матрицы имеет вид (0 1 1 1 0 0). Заполняя аналогично остальные строки, получаем матрицу вида: . Для построения матрицы смежности ребер и матрицы инциденций рассмотрим не взвешенный граф, предварительно занумеровав ребра графа произвольным образом. Так как граф имеет девять ребер, то матрица смежности ребер является квадратной матрицей девятого порядка. Ребро u 1 имеет общую вершину с ребрами u 3 и u 5 , а также общую вершину с ребрами u 2 и u 4 . Поэтому первая строка матрицы имеет вид (0 1 1 1 1 0 0 0 0). Заполняем аналогично остальные строки, получаем матрицу вида:
. Граф имеет шесть вершин и девять ребер, поэтому матрица инциденций является матрицей размерности 6  9. Поскольку вершина инцидентна ребрам , и , и не инцидентна остальным ребрам, то первая строка матрицы имеет вид (0 0 1 1 0 0 1 0 0). Остальные строки матрицы заполняем аналогично. Следовательно, матрица имеет вид: . 3) Для того, чтобы найти число остовных деревьев, сначала составим матрицу Кирхгофа. .
Используя теорему Кирхгофа, найдем, например, алгебраическое дополнение элемента . =  четвертую и пятую строчки оставляем, третью умножаем на (  1) и складываем со второй, потом третью умножаем на 3 и складываем с первой  = . Таким образом, для данного графа можно построить 64 остовного дерева. 4) Для построения минимального остовного (корневого) дерева рассмотрим взвешенный граф, данный в условии задачи. Используем для построения остовного дерева алгоритм В графе выбираем ребро с
минимальным весом. В нашем случае это ребро, соединяющее вершины и с весом, равным 4. Пусть, например, вершина будет корнем дерева. Далее выбираем ребра, инцидентные вершинам , и имеющие минимальный вес. Таким является ребро с весом 5, соединяющее вершины и . Включаем его в строящееся дерево. Затем к вершине присоединяем ребро с весом 7, соединяющее вершины и . К вершине присоединяем ребро с весом 7, соединяющее вершины и . И в заключение, к вершине присоединяем ребро с весом 6, соединяющее вершины и . Таким образом, получаем минимальное остовное дерево (рис. 1). Минимальный вес построенного дерева равен:  min (T)=4+5+7+7+6=29. Так как мы в качестве корня дерева выбрали вершину , то высота дерева будет равна h(T)=4. Замечание. Если бы в качестве корня выбрали вершину , то высота дерева была бы равна h(T)=5. ИЛИ Построим минимальное корневое остовное дерево данного взвешенного графа с помощью алгоритма Прима. Выбираем вершину , которая будет корнем дерева. Из трех ребер, которые инцидентны вершине , выбираем те, что имеют наименьший вес. Два ребра с весом, равным 7, инцидентны вершине . Присоединяем эти ребра к выбранной вершине. К вершине присоединяем ребро с весом 5, соединяющее вершины и . К вершине присоединяем ребро с весом 4, соединяющее вершины и . К вершине присоединяем ребро с весом 6, соединяющее вершины и .Таким образом, получаем следующее минимальное корневое дерево с весом, равным  min (T)=7+7+6+5+4=29. Высота построенного дерева равна h(T)=3.

Ответ.
1) d(v 1 )=3, d(v 2 )=3, d(v 3 )=4, d(v 4 )=3, d(v 5 )=2, d(v 6 )=3; 3) число остовных деревьев равно 64; 4) минимальный вес дерева равен  min (T)=29, высота равна h(T)=4. Голованёва Любовь Викторовна, учитель математики
Статья отнесена к разделу:
Внеклассная работа
1.

Методические

рекомендации

к

теме



Графы

”.
Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая. Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести
занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).
2.

Теоретический

материал

к

теме



Графы

”.

Введение
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.
Понятие графа
Рассмотрим две задачи.
Задача 1.
Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ? Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями. Теперь сразу видно, что долететь с Земли до Марса нельзя.
Задача 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? Рис. 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 раз?