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

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Графы

1.1 Начальные понятия

1.2 Деревья

1.3 Связность

1.4 Гамильтоновы графы

Глава 2. Степенные последовательности

2.1 Графическая последовательность

2.2 Критерии графической последовательности

2.3 Реализация графической последовательности с максимальной связностью

2.4 Гамильтонова реализация графической последовательности

Заключение

Список литературы

Приложение

Введение

Начало теории графов все единодушно относят к 1736 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла, как теперь его называют). Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине 19 века инженер-электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А. Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев.

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

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

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

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

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

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

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

Глава 1. Графы

1.1 Начальные понятия

Термин "граф" впервые появился в книге выдающегося венгерского математика Д. Кенига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (18 в.). [1, c. 7]

Как правило, специалисты по теории графов в своих работах используют свою собственную терминологию. Даже само понятие "граф" не воспринимается однозначно. Некоторые авторы действительно определяют "граф" как простой граф (конечные неориентированные графы без петель и кратных ребер), другие же имеют в виду такие понятия, как мультиграф, псевдограф, ориентированный граф или сеть [F. Harari, 1969].

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

В качестве примера приведем некоторые известные определения графа. Емеличев В.. Мельников О. 1990:

Пусть V-непустое множество, - множество всех его двухэлементных подмножеств. Пара (V, E), где E - произвольное подмножество множества , называется графом (неориентированным графом).

Харари. 1969:

Граф G состоит из конечного непустого множества V, содержащего р вершин, и заданного множества X, содержащего q неупорядоченных пар различных вершин из V. Каждою пару x={u, v} вершин в X называют ребром графа G и говорят, что х соединяет к и v.

В моей работе рассматриваются только конечные графы, т.е. множество V предполагается конечным, хотя в определении графа конечность этого множества не требуется. Элементы множества V называются вершинами графа, а элементы множества Е-ребрами. Итак, граф-это конечное множество V вершин и множество Е ребер, . Множества вершин и ребер графа G обозначаются символами VG и EG соответственно. Вершины и ребра графа называются его элементами. Число |VG| вершин графа G называется его порядком и обозначается через |G|. Если |G|=n, |EG|=m, то G называются (n,m)-графом.

Говорят, что две вершины u и графа смежны, если множество {u,} является ребром, и не смежным в противном случае. Если е={u,}-ребро, то вершины u и называют его концами. В этой ситуации говорят также, что ребро е соединяет вершины u и . Такое ребро обозначается символом u.

Два ребра называются смежными, если они имеют общий конец.

Вершина и ребра е называются инцидентными, если является концом ребра е (т.е. е=u), и не инцидентными в противном случае.

Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.

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

Графы удобно изображать в виде рисунком, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии-ребрам. В качестве иллюстрации рассмотрим граф G, изображенный на рис. 1.1. это (5, 6)-граф, VG={1, 2, 3, 4, 5}, EG={{1, 2}, {1, 5},{2, 3}, {2, 4}, {2, 5}, {4, 5}}. Вершины 1 и 2 смежны, а 1 и 3 не смежны. Вершины 1 и ребро {1, 2} инцидентны. N(2)={1, 3, 4, 5}.



Рис. 1.1

Рис. 1.2

Приведем примеры некоторых графов специального вида.

Рис. 1.3

Граф G называется полным, если любые две его вершины смежны, т. е. EG=(VG). Полный граф порядка n обозначается символом , число ребер в нем равно . На рис.1.2 изображены графы , .

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

Красивыми примерами являются графы пяти платоновых тел (т.е. правильных многогранников): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра (рис. 1.3).

Ниже неоднократно используются термины "разбиение" и "покрытие". Набор подмножеств множества S называется покрытием множества S, если объединение этих подмножеств совпадает с S. Покрытие называется разбиением, если никакие два из входящих в него подмножества не пересекаются.

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

Рис. 1.4

Иногда приведенное выше определение графа оказывается недостаточным и приходится рассматривать более общие объекты, в которых две вершины могут соединяться более чем одним ребром. Так возникает понятие "мультиграф". Мультиграф-это пара (V, E), где V-непустое множество (вершин), а Е-семейство подмножеств множества (ребер). Употребление термина "семейство" вместо "множества" означает, что элементы множества могут в E повторяться, т.е. допускаются кратные ребра. Дальнейшее обобщение состоит в том. Что кроме кратных ребер допускаются еще петли, т.е. ребра, соединяющие вершину саму с собой. Псевдограф-это пара (V, E), где V-непустое множество (вершин), а Е-некоторое семейство неупорядоченных пар вершин (ребер), не обязательно различных. На рис 1.4 изображены мультиграф и псевдограф.



Рис. 1.5

Ориентированный граф (или ортограф)-это пара (V, А), где V-множество вершин, А-множество ориентированных ребер, которые называются дугами, . На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу (рис. 1.15).

Рис. 1.6

1.2 Деревья

Деревом называется связный граф, не содержащий циклов, Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. На рис.1.6 изображены все деревья шестого порядка.

Рис. 1.7

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

Теорема 1.1 Для (n, m)-графа G следующие утверждения эквивалентны:

1) G-дерево;

2) G-связный граф и m=n-1;

3) G-ациклический граф и m=n-1;

4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;

5) G-циклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

Следствие 1.1 В любом дереве порядка n2 имеется не менее двух концевых вершин.

Следствие 1.2 Граф G является лесом тогда и только тогда, когда (G)=0.

Следствие 1.3 Граф G имеет единственный цикл тогда и только тогда, когда (G)=1.

Следствие 1.4 Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.

Теорема 1.2 Центр любого дерева состоит из одной или из двух смежных вершин.

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

Теорема Кирхгофа (1847). Число остовных деревьев в связном графе G порядка равно алгебраическому дополнению любого элемента матрицы Кирхгофа B(G).

1.3 Связность

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

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

Граф G, представленный на рис. 1.7, связен, но его связность можно нарушить, удалив вершину 4. Поэтому =1. Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее трех ребер. Например, G распадается на две компоненты при удалении ребер {4, 5}, {4, 6}, {4, 7}.

Рис. 1.8

Пусть G-граф порядка n>1. Числом реберной связности графа G назовем наименьшее число ребер, удаление которых приводит к несвязному графу. Число реберной связности графа будем считать равным нулю, если этот граф одновершинный.

1.4 Гамильтоновы графы

Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу "кругосветного путешествия" по додекаэдру (рис. 1.9), узловые вершины которого символизировали крупнейшие города Земли, а рёбра - соединяющие их дороги.

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



Рис. 1.9. Граф додекаэдра с выделенным циклом Гамильтона

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

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

Теорема 1.3. Каждый негамильтонов двусвязный граф содержит тэта-подграф.

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

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

Теорема 1.4 (В. Хватал, 1972 г.). Граф со степенной последовательностью является гамильтоновым, если для всякого k, удовлетворяющего неравенствам , истинна импликация .

Теорема 1.5 (О. Оре, 1960 г.). Если для любой пары u и несмежных вершин графа G порядка выполняется неравенство degu+degn, то G-гамильтонов граф.

Теорема 1.6 (Г. Дирак, 1952 г.). Если |G|=n3 и для любой вершины графа G выполняется неравенство degn/2, то G-гамильтонов граф.

Теорема 1.7 (У. Татт, 1946 г.). Всякий 4-связный планарный граф является гамильтоновым.

Глава 2. Степенные последовательности

Эта глава посвящена теории степенных последовательностей.

Степенной последовательностью графа называется список степеней его вершин.

Часто по степеням вершин графа можно судить о его строении. Например, граф, в котором полусумма степеней вершин (т.е. число ребер) не меньше числа вершин, содержит цикл и т.д.

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

Изучение этих вопросов не только продиктовано внутренней логикой развития теории графов, но имеет и практическое значение. Если в виде графа представляется коммуникационная схема, узлам которой соответствуют вершины графа, а ребрам - каналы связей между вершинами и, например, максимально возможной связью. Такой граф соответствовал бы схеме с заданными пропускными способностями узлов и максимальной надежностью. Одна из исторически первых задач теории графов также относится к этому кругу проблем. Именно, в 1857 году А. Кэли, изучая насыщенные углеводороды, пришел к задаче перечисления деревьев, степени вершин которых равны 1 и 4.

2.1 Графическая последовательность

Последовательность целых неотрицательных чисел ниже называется n-последовательностью и обозначается одной буквой d. n-последовательностью d называется графической, если существует граф, степенная последовательность которого совпадает с d. Этот граф называется реализацией последовательности d.

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

Назовем n-последовательность d правильной, если выполняются два следующих условия:

1) ,

2) --четное число.

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

Иногда последовательность d удобно записывать в виде , где числа попарно различны, а показатель означает количество повторений числа в последовательности d . Так, .

Рассмотрим последовательность ). Существуют ровно пять графов, являющихся реализациями последовательности d. Они имеют следующие компоненты: 1) и , 2) , и , 3) и , 4) и , 5) и .

В общем случае графическая последовательность имеет много реализаций и их число определить сложно. В установлении связи между этими реализациями важную роль играет вводимое ниже понятие переключения. Пусть G - граф, a, b, c, d -- четыре его попарно различные вершины, причем abEG, cdEG, acEG, но bdEG. Тогда говорят, что граф G допускает переключение s=(ab, cd). Полученный в результате переключения s граф обозначается через sG; граф G превращается в sG в результате удаления ребер ab и cd и присоединения ребер ac и bd: sG=G-ab-cd+ac+bd. Обратное переключение =(ac, bd)применимо к графу sG. Тождественные преобразования ребер графа также по определению является переключением.

Например, на рис. 2.1 изображены графы G и sG, где s=({1, 3}, {4, 2}).

Рис. 2.1

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

Теорема 2.1. Любая реализация графической последовательности

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

Доказательство этой теоремы основано на следующей лемме.

Лемма 2.1. Пусть G - граф, вершины которого занумерованы числами 1, 2, …, n в порядке возрастания степеней:

VG={1, 2, …,n}, deg i=, , i=

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



Пусть i, j, kVG, j>k, ijEG, ikEG. Так как то существует четвертая вершина l, смежная с k , но не смежная с j (рис. 2.3, где, как и всюду в этой главе, пунктирными линиями обозначены ребра, отсутствующие в графе). Следовательно, граф G допускает переключение s=(ij, kl) . Если , то ik, ij. Сделав несколько подобных переключений, придем к нужному графу H.

Рис. 2.3

Доказательство теоремы 2.1. Пусть d - правильная графическая n-последовательность. Воспользуемся индукцией по n4. Как подтверждает прямая проверка, при n4 каждая графическая последовательность имеет только одну реализацию. Следовательно, для n4 утверждение теоремы правильно. Пусть n>4 и это утверждение верно для всех графических (n-1) -последовательностей. Пусть, далее, и --две реализации последовательности d. Для каждого из графов и обозначим через какую-либо вершину степени . Согласно лемме 1.2 существуют такие цепочки переключений …, и ,…,, что в графах и окружения вершины состоят из вершин степеней Поэтому степенные последовательности графов и совпадают. По индуктивному предположению существует такая цепочка переключений , что .

Эти переключения не затрагивают вершины , поэтому . Далее имеем

. >

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

2.2 Критерии графичности последовательности

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

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

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

Пусть d-правильная n-последовательность, n>1. Зафиксируем индекс i, , и через обозначим (n-1)- последовательность, которая получается из последовательности d вычеркиванием i-го члена. Тем самым

,

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

Тогда называется произвольной последовательностью.

Например, если d=(3, 3, 1, 1), то =(2, 0, 0)=, =(2, 3, 1)=.

Теорема 2.2 Пусть d-правильная последовательность, n<1. Если для какого-нибудь индекса i, , произвольная последовательность является графической, то и d-графическая последовательность. Если последовательность d графическая, то каждая последовательность является графической.

Пусть --графическая последовательность, H-ее реализация. Добавим к графу H новую вершину и соединив ее ребрами с вершинами наибольших степеней, получим реализацию последовательностей d. Следовательно, d--графическая последовательность.

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

Предыдущий критерий вместе с леммой 2.1 подсказывают алгоритм распознавания графичности правильной последовательности и построения одной из ее реализаций. Назовем этот алгоритм l-процедурой Пусть d--правильная n-последовательность, V-n-элементное множество вершин (будущего графа), каждому элементу которого приписано неотрицательное целое число d()--метка, причем d()<n. Пусть, далее, S()-подмножество V, составленное из d() отличных от вершины вершин с максимальными метками (S() определено не однозначно).

Шаг l-процедуры заключается в следующем:

1) фиксировать произвольную вершину с положительной меткой (далее эта вершина называется ведущей);

2) фиксировать одно из подмножеств S();

3) вершину соединить ребром с каждой вершиной из S();

4) изменить метки вершины и каждой из вершин u, входящих в S(), положив d():=0, d(u):=d(u)-1.

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

l-процедура применяется к правильной n-последовательности d и заключается в последовательном выполнении шагов. Берем V={1, 2, …, n) и первоначально полагаем d(i)=. Из леммы 2.1 вытекает, что возможно одно из двух: либо мы приходим к нулевой последовательности меток и одновременно получаем реализацию последовательности d, либо очередной шаг проваливается, т. е. последовательность d не является графической.

На рис. 2.4 l-процедура демонстрируется на примере последовательности . Каждый столбец на этом рисунке соответствует одному шагу l процедуры

граф алгоритм символьны maple

Рис. 2.4

2.3 Реализация графической последовательности с максимальной связностью

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

Пусть d--правильная графическая n-последовательность. Поскольку для любого графа G (минимальная степень вершин), то мы стремимся построить реализацию G последовательности

d с .

Вначале построим просто связную реализацию.

Теорема 2.3 Правильная графическая n-последовательность может быть d реализована связным графом тогда и только тогда, когда и верно неравенство

. (1)

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

Замечание. При неравенство (1) выполняется автоматически.

Необходимость условий теоремы очевидна. В самом деле, связанный граф порядка n не имеет изолированных вершин и число ребер в нем не менее n-1. Из леммы о рукопожатиях вытекает неравенство (1).

Достаточность докажем индукцией по длине последовательности d. При n=2 условиям теоремы удовлетворяет только одна последовательность . Реализацией этой последовательности служит связный граф , стало быть, для n=2 теорема верна. Пусть теперь n>2 и доказываемое утверждение верно для графических последовательностей, длины которых меньше n. Отдельно рассмотрим два случая: 1) , 2) .

1) . Так как n>2, то из неравенства (1) вытекает, что . Рассмотрим производную последовательность

i=.

Поскольку , ,

то последовательность удовлетворяет условиям теоремы.

2) . Снова будем различать две ситуации:

а) и б) .

В ситуации а) из условий теоремы следует, что

Для произвольной последовательности имеем

В ситуации б) для произвольной последовательности получаем

 .

Итак, в любой ситуации производная последовательность удовлетворяет условиям теоремы и по индуктивному предположению имеет связную реализацию H, получаемую в результате описаний в формулировке теоремы l-процедуры. Добавив к графу H новую вершину, смежную с вершинами степеней , получим связную реализацию последовательности d.>

Аналогично доказывается

Теорема 2.4 n-последовательность d может быть реализована деревом тогда и только тогда, когда она не содержит нулей и верно равенство .

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

На рис. 2.5 показана процедура, строящая дерево, которое является реализацией последовательности .

Рис. 2.5

Перейдем к графам с более высоким числом реберной связности. Приведем без доказательств следующую теорему.

Теорема 2.5. Каждая правильная графическая n-последовательность в с имеет реализацию, число реберной связности которой равно . Такая реализация строится l-процедурой, на каждом шаге которой ведущей является вершина с минимальной с положительной меткой.

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

2.4 Гамильтонова реализация графической последовательности

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

В формулировке следующего утверждения используется обозначение S().

Теорема 2.6.

Если существует реализация правильной n-последовательности d, имеющая гамильтонову цепь с началом в вершине степени, то к такой реализации приведет l-процедура, на первом шаге которой ведущей является вершина степени , а на каждом из последующих-вершина с минимальной положительной меткой из множества S(), где --вершина, ведущая на предыдущем шаге.

Доказательство этой теоремы требует перебора возможных вариантов и потому громоздко; здесь оно опускается.

Перейдем к построению гамильтоновой реализации.

Оно основано на следующей теореме.

Теорема 2.7. Для того чтобы правильная n-последовательность d имела реализацию в виде гамильтонова графа, необходимо и достаточно выполнение следующих двух условий:

1) ;

2) существует реализация последовательности d, имеющая гамильтонову цепь с началом в вершине степени .

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

Пусть . Тогда вершина смежна с какой-либо вершиной , где 1<i<n-1. Рассмотрим вершину . Если , то - гамильтонов цикл. Пусть теперь . Поскольку вершина смежна как с , так и с , а вершина не смежна ни с , ни с , хотя , то существует такая вершина , что k2, , . Но тогда граф G допускает переключение . Граф sG имеет гамильтонов цикл >

На рис. 2.6. показана процедура построения гамильтоновой реализации последовательности . Получен граф G с гамильтоновой цепью (1, 3, 2, 5, 6, 4); (1, 3, 2, 5, 6, 4, 1)-гамильтонов цикл.

Рис. 2.6

Заключение

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

В практической части были изучены и решены задачи на построение неориентированных графов с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами в задачах-турнирах.

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

Реализованы алгоритмы построения связных графов и деревьев в пакете символьной математики Maple.

Список литературы

1. Емеличев В.А. Мельников О.И. Лекции по теории графов. М.: Наука 1990.

2. Уилсон Р. Введение в теорию графов. М.: Мир 1977.

3. Мельников О.И. Занимательные задачи по теории графов. Мн.: ТетраСистемс 2001.

4. Оре О. Теория графов. М.: Наука 1980.

5. Маршалл А., Олкин И. "Неравенства. Теория мажоризации и ее приложения". М.: Мир, 1983

6. Заславский А., Френкин Б., Толпыго А., Токарев С. "Математика турниров." http://turgor.ru/lktg/2005/2/index.htm

7. Кирсанов М.Н. "Графы в Maple" М.: Физматлит, 2007.

8. Кормен Т.М. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ Издательский дом "Вильямс", 2006.

9. Дьяконов В.П. "Maple 9.5/10 в математике, физике и образовании". Солон-Пресс 2006

Приложение

Задача 1.

В шахматном турнире принимает участие 7 школьников. Может ли быть так, чтобы:

а) Ваня сыграл 7 партий, Толя - 5, Леша и Дима - по 4, Семен и Илья - по 3, Женя - 2;

б) Ваня сыграл 5 партий, Толя, Леша и Дима - по 4, Семен и Илья - по 3, Женя - 2;

в) Ваня сыграл 6 партий, Толя, Леша и Дима - по 4, Семен - 2, Илья и Женя - по одной;

г) Ваня сыграл 5 партий, Толя и Леша - по 4, Дима - 3, Семен, Илья и Женя - по 2?

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

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

Рассмотрим последовательность (7,5,4,4,3,3,2), (5,4,4,4,3,3,2), (6,4,4,4,2,1,1), (5,4,4,3,2,2,2) из условий задачи и выясним, какие из них являются графическими.

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

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

Определение графичности третьей и четвертой последовательностей более сложное.

Назовем последовательности D правильной, если выполняются два условия:

1) ;

2) сумма всех членов последовательности - четное число.

Ш Теорема. Пусть -- правильная последовательность и , …, …, -- последовательность, полученная из D. Тогда последовательность D является графической тогда и только тогда, когда графической является последовательность .

(Для получения последовательности из D нужно вычесть по единице у членов последовательности D, начиная со второго. Последовательность D может оказаться неправильной. Примеры перехода от D к : D=(5,5,4.3,3,2.2), =(4,3,2,2,1,2), D=(3,2,2,1), =(1,1,0).)

Доказательство теоремы.

Пусть D'-графическая последовательность и граф H-ее реализация.

Добавив к H новую вершину и соединив ее ребрами с вершинами степеней

d2-1,d3-1,…, dd+1-1, получим реализацию последовательности D.

Пусть теперь D-графическая последовательность и граф G-ее реализация.

Если вершина v1 смежна с вершинами v2,v3,…,vd-1, то удалив v1 вместе с выходящими из нее ребрами, получим реализацию последовательности D'.

Пусть во всех реализациях последовательности D вершина v1 не смежна с какой-то вершиной из множества v2,…,vd+1 .Среди реализаций выберем такой граф G,в котором первая вершина , не смежная с v1 будет иметь наименьший номер. Пусть это будет вершина vp. Через v1 обозначим вершину с большим номером, смежную с вершиной v1. Так как для степеней вершин выполняется неравенство d(vp)?d(v1), то существует вершина vx , смежная с вершиной v1. (рис. 1)

Рис. 1

Построим граф G' ,заменив в G ребра (vp, vs) и (v1, vi) на ребра (v1, vp) и (vs, vi) (см. рис. 2)

Рис. 2

В получившимся графе G' множество степеней вершин то же, что и в графе G , т.е. G' - реализация последовательности. Но в этой реализации вершина v1 смежна с вершиной vр, что противоречит выбору графа G.

Теорема доказана.

Доказанная теорема позволяет предложить алгоритм распознавания графичности последовательности. Для последовательности D строим последовательность D', по указанному ранее правилу. Упорядочив последовательность D', получаем последовательность D1. Для D1 строим D1 и т.д. Процесс продолжается до тех пор, пока не получается заведомо графическая последовательность, например, состоящая из одних нулей (тогда исходная последовательность графическая), или в последовательности не оказываются отрицательные числа (тогда исходная последовательность не является графической)

Рассмотрим третью последовательность и проделаем указанные преобразования:

= (6,4,4,4,2,1,1),

= = (3,3,3,1,0,0),

= = (2,2,0,0,0),

= (1,-1,0,0).

Так как в последовательности есть отрицательные числа, то последовательность (6,4,4,4,2,1,1) не является графической.

Рассмотрим четвертую последовательность и проделаем указанные преобразования:

= {5, 4, 4, 3, 2, 2, 2},

= {3, 3, 2, 1, 1, 2}.

Превратим последовательность в правильную:

= (3, 3, 2, 2, 1, 1),

== (2, 1, 1, 1, 1),

= (0, 0, 1, 1).

Последовательность графическая, ее реализация:

Рис. 3

Будем по очереди возвращать удаленные вершины:



Рис. 4

Рис. 5

Рис. 6

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

Задача 2.

Может ли существовать шахматный турнир, в какой-то момент которого есть игроки, сыгравшие только 7, 5, 3, 2 партии? Какое наименьшее число игроков может участвовать в таком турнире?

Решение: решение задачи сводится к ответам на два вопроса. Существует ли граф, у которого есть вершины степеней 7, 4, 3, 2 и нет вершин других степеней?

Какое наименьшее число вершин может быть в таком графе?

Ответ на первый вопрос совсем прост: граф, который является объединением полных графов , , и имеет вершины указанных степеней. Такой граф содержит 20 вершин.

Теперь построим граф G, который имеет наименьшее число вершин. Вершины графа G можно разбить на два множества: А и В. Множество А состоит из вершин полных графов и , множество В - из вершин пустых графов и . Каждая вершина графа соединена ребром с каждой из остальных вершин графа G. Кроме того, каждая вершина графа соединена ребром с каждой вершиной графа . (Схема соединения вершин графа на рис. 7).

Рис. 7

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

+ + + = 7 (степень вершины, принадлежащей )

+ + = 4 (степень вершины, принадлежащей )

+ + = 3 (степень вершины, принадлежащей )

+ = 2 (степень вершины, принадлежащей )

Решив эту систему, получим: =2, =1, =2, =3. Граф G изображен на рис. 8.

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



Рис. 8

Задача 3.

Борцовский турнир с 13 участниками проводится по олимпийской системе, при которой проигравший выбывает. На одну встречу, с учетом подготовки к ней, и отдыха участников отводится час. Сколько времени нужно, чтобы провести турнир, если в распоряжении организаторов только 5 борцовских ковров?

Решение.

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

Рис. 9

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

Задача 4

В волейбольном турнире, проводимом по круговой системе, участвуют 7 команд.

Может ли оказаться, что команды одержали:

1) первая-6 побед, вторая и третья-по 5, четвертая и пятая-по 2,шестая и седьмая-по одной победе;

2) первая, вторая и третья-по 5 побед,четвертая-4,пятая и шестая-по одной, седьмая-ни одной победы?

Решение.

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

В случае а) задача решается просто. Турнир с семью вершинами получается из полного графа К7 ориентацией каждого ребра. Поэтому сумма полустепенен его вершин равна числу ребер графа К7, т.е. (7х6):2 = 21. Сумма же чисел побед равна 22. Поэтому такого турнира быть не может.

В случае б) сумма чисел побед равна 21. и решение задачи более сложное. Поставим в соответствие любому волейбольному турниру с n участниками двудольный граф G,в котором доля А = {1',2',..., n'}, доля В = {1", 2",...,n"). Ребро в графе G соединяет вершины i' и j', тогда и только тогда, когда команда i выиграла у команды j (пример графа G для четырех команд см. на рис. 10).



Рис. 10

Степень вершины i' графа G равна числу побед команды i, а степень вершины j' равна числу поражений команды j . Если волейбольный турнир с указанным числом побед существует, то существует двудольный граф G, у которого степени вершин доли А будут 5, 5, 5, 4, 1, 1, 0 а доли В - 1, 1, 1, 2, 5, 5, 6 (числа поражений команд).

От графа G перейдем к графу G1 ,соединив каждую пару вершин доли

А ребром (см. рис. 11).

Рис. 11

Если волейбольный турнир с указанным числом побед существует, то существует граф G1, степени вершин которого будут: 11, 11, 11, 10, 7, 7, 6, 1, 1, 1, 2, 5, 5, 6.

Воспользуемся предложенным в задаче 1 способом проверки графичности последовательности

D = (11, 11,11,10,7,7,6,6,5,5,2,1,1,1).

Рассмотрим цепочку последовательностей:

Так как в последовательности D'2 появилось отрицательное число, то последовательность D не является графической. Поэтому не существует нужный граф G1, и. следовательно, волейбольный турнир с указанным числом побед.

Размещено на Allbest.ru

...