Теория графов - Контрольная работа

Начало теории графов все единодушно относят к 1736 г., когда Л. Эйлер не только решил популярную в то время задачу о кенигсбергских мостах, но и нашел критерий существования в графе специального маршрута (эйлерова цикла, как теперь его называют). Однако этот результат более ста лет оставался единственным результатом теории графов. Всякий граф состоит из конечного числа вершин и ребер, соединяющих некоторые вершины. Первая проблема - определить, является ли заданная конечная последовательность неотрицательных целых чисел графичной, то есть существует ли граф.Некоторые авторы действительно определяют "граф" как простой граф (конечные неориентированные графы без петель и кратных ребер), другие же имеют в виду такие понятия, как мультиграф, псевдограф, ориентированный граф или сеть [F. Пара (V, E), где E - произвольное подмножество множества , называется графом (неориентированным графом). 1969: Граф G состоит из конечного непустого множества V, содержащего р вершин, и заданного множества X, содержащего q неупорядоченных пар различных вершин из V. В моей работе рассматриваются только конечные графы, т.е. множество V предполагается конечным, хотя в определении графа конечность этого множества не требуется. Говорят, что две вершины u и графа смежны, если множество {u, } является ребром, и не смежным в противном случае.Деревом называется связный граф, не содержащий циклов, Любой граф без циклов называется ациклическим (или лесом). На рис.1.6 изображены все деревья шестого порядка. Существует несколько вариантов определения дерева; некоторые из них отображены в следующей теореме. 5) G-циклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. Следствие 1.4 Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.Связный граф был определен как граф, у которого любые две вершины соединены цепью Числом вершинной связности (или просто числом связности) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее трех ребер.Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Не все связные графы гамильтоновы хотя бы потому, что такой граф должен быть двусвязным. Любой граф, содержащий две вершины степеней 3, соединенных тремя простыми попарно непересекающимися цепями длины не менее двух, называется тета-графом. Интуитивно ясно, что если граф содержит много ребер и эти ребра к тому же достаточно равномерно распределены, то граф "предрасположен" быть гамильтоновым.Степенной последовательностью графа называется список степеней его вершин. Часто по степеням вершин графа можно судить о его строении. Например, граф, в котором полусумма степеней вершин (т.е. число ребер) не меньше числа вершин, содержит цикл и т.д. Можно ли построить граф с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами и как это делать?Последовательность целых неотрицательных чисел ниже называется n-последовательностью и обозначается одной буквой d. n-последовательностью d называется графической, если существует граф, степенная последовательность которого совпадает с d. Очевидно, что порядок членов в графической n-последовательности d несущественен, а каждый ее член удовлетворяет неравенствам Часто удобно эти последовательности считать невозрастающими. Назовем n-последовательность d правильной, если выполняются два следующих условия: 1) , 2)-четное число. Иногда последовательность d удобно записывать в виде , где числа попарно различны, а показатель означает количество повторений числа в последовательности d . Полученный в результате переключения s граф обозначается через SG; граф G превращается в SG в результате удаления ребер ab и cd и присоединения ребер ac и bd: SG=G-ab-cd ac bd.Ее можно организовать так, чтобы она строила реализацию с некоторыми предписанными свойствами, если, конечно, такие реализации существуют. Ниже показано, как с помощью l-процедуры построить такую реализацию G графической последовательности, число реберной связности которой максимально среди всех реализаций. Поскольку для любого графа G (минимальная степень вершин), то мы стремимся построить реализацию G последовательности d с . Теорема 2.3 Правильная графическая n-последовательность может быть d реализована связным графом тогда и только тогда, когда и верно неравенство Если указанные условия выполняются, то l-процедура, на каждом шаге которой ведущей является вершина с минимальной положительной меткой, приводит к связному графу.В этом параграфе будет показано, как с помощью l-процедуры построить реализацию графической последовательности, обладающую гамильтоновой цепью или гамильтоновым циклом, если такие реализации существуют.

Содержание

Введение

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

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

1.2 Деревья

1.3 Связность

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

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

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

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

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

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

Заключение

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

Приложение