ГРАФОВ ТЕОРИЯ, раздел дискретной математики, в котором изучаются свойства графов и их обобщений. Графом называется пара (V, Е), где V - множество точек, называемых вершинами, и Е - множество пар вершин, причём если порядок, в котором перечислены вершины в паре, не важен, то эта пара вершин графа называется ребром, а если важен - дугой. Граф, содержащий только рёбра, называется неориентированным графом, или просто графом, а граф, содержащий только дуги, - ориентированным графом. На рисунке 1 - неориентированный граф с вершинами а, b, с, d и рёбрами (а, b), (b, с), (с, d), (а, d), (а, с), (b, d), на рисунке 2 - ориентированный граф с вершинами а, b, с, d, е, f и дугами (а, b), (b, с), (с, d), (d, е), (е, f), (f, а).
Исторический очерк. Первые задачи графов теории были связаны с решением математических задач развлекательного характера и головоломок (смотри Комбинаторные задачи классические). Одним из первых результатов графов теории был критерий существования обхода всех рёбер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кёнигсбергских мостах (смотри Гамильтонов цикл). С середины 19 века появляются относящиеся к графов теории работы, содержащие результаты, связанные с различными приложениями математики. Так, Г. Кирхгоф (1847) для составления полной системы уравнений для токов и напряжений в электрических сетях (смотри Кирхгофа правила) предложил представлять такую сеть графом и находить в этом графе остовные деревья, что приводит к решению задачи выделения независимых систем уравнений. Деревом называется связный граф, не содержащий циклов (рис. 3), остовное дерево графа - это его подграф, представляющий собой дерево, множество вершин которого совпадает с множеством вершин графа.
А.Кэли (1854) для подсчёта числа изомеров предельных углеводородов пришёл к задачам описания и перечисления деревьев, обладающих заданными свойствами. Термин «граф» утвердился в математике после выхода монографии немецкого математика Д. Кёнига (1936). Начиная со 2-й половины 20 века значительно расширились исследования в графов теории, в основном в силу развития дискретной математики и вычислительной техники. Задание графа равносильно заданию на элементах множества вершин V некоторого бинарного отношения. По этой причине, а также ввиду возможности наглядного представления графа в виде чертежа на плоскости, графовые модели используются при построении алгоритмов решения разнообразных задач как в математике и естествознании, так и в гуманитарных науках.
Методы исследования в теории графов. Прежде всего, выделяются комбинаторные методы теоретико-множественного анализа заданного бинарного отношения на множестве вершин. Весьма существенны (особенно в перечислительных задачах) алгебраические методы, в первую очередь методы теории групп (в частности, групп подстановок). При изучении укладок графа на плоскость привлекаются результаты топологического характера. Случайные графы изучаются с помощью теоретико-вероятностных методов.
Особую роль при изучении графов играют матричные методы. Для графа G матрицей смежности А = A(G) = ||a ij || называется матрица, в которой a ij = 1, если в графе G вершина i связана с вершиной j ребром (или дугой в ориентированном графе) и a ij = 0 в противном случае. В первом случае говорят, что вершины i и j смежны, во втором случае - что они несмежны. Маршрутом в графе G называется последовательность ν 0 e 1 ν 1 ...ν n -1 e n ν n , состоящая попеременно из вершин и рёбер графа, в которой ребро е i соединяет вершины v i -1 и v i , i= l, ..., n; говорят, что этот маршрут связывает вершины v 0 и v n . Маршрут, в котором v 0 = v n , называется циклом. Маршрут называется цепью (соответственно, простой цепью), если все его рёбра (все его вершины) различны. При n≥ 1 элемент на месте (i, j) в матрице А n равен числу маршрутов длины n из вершины v i в вершину v j . Граф называется связным, если для любых его двух вершин существует маршрут, связывающий эти вершины. Для графа G с р вершинами и q рёбрами, в котором занумерованы как вершины, так и рёбра, рассматривается матрица инцидентности В(G), представляющая собой матрицу, состоящую из нулей и единиц с двумя единицами в каждом столбце; в столбце, соответствующем ребру, соединяющему вершины i и j, единица стоит в строках с номерами i и j. Говорят, что каждая из вершин i и j и соединяющее их ребро инцидентны, два ребра смежны, если они имеют общую инцидентную им вершину. Ранг матрицы инцидентности В(G) равен р 1 , если граф G является связным графом.
Множество собственных значений матрицы смежности графа или ориентированного графа (при этом каждое значение берётся столько раз, какова его кратность) называется спектром графа. Спектр графа с и вершинами состоит из n действительных чисел. Изучение спектра графа позволяет выяснить многие особенности его строения.
Задачи теории графов. Центральным в графов теории является раздел, изучающий структурные свойства графов. Одной из характеристик структуры графа является последовательность степеней его вершин. Степенью вершины неориентированного графа называется число инцидентных ей рёбер. Графическим разбиением чётного натурального числа n называется представление его в виде суммы р слагаемых n = ∑ p i =1 d i такое, что существует граф с р вершинами, степени которых равны d 1 ,...,d p . В графов теории известен эффективный алгоритм, позволяющий для данного упорядоченного набора чисел (d 1 ,...,d p) определить, существует ли граф с р вершинами v 1 ,...,v p , для которых последовательность степеней (d(v 1), ..., d(v p)) совпадает с этим набором. Подробно изучено другое важное структурное свойство - связность графа, а также вопросы, относящиеся к существованию в связном графе маршрутов определённого вида.
Специальным разделом структурной графов теории является факторизация графа, т. е. разложение графа G = (V, Е) на сумму факторов (подграфов) G 1 , ..., G m с некоторым заданным свойством, где G i = (V, Е i) и Е = Е 1 u...uЕ m - разбиение множества рёбер на непустые непересекающиеся подмножества. Наиболее распространённые виды факторизации: n-факторизация, где G i - однородные графы степени n (графы, степени всех вершин которых одинаковы и равны n), и древесная факторизация, где каждая компонента любого G i , i=1, ...,m, является деревом. Любой полный граф К 2 n , т. е. граф, в котором любые две вершины смежны, 1-факторизуем, но не 2-факторизуем; любой полный граф К 2 n+1 не является 1-факторизуемым, но представляется в виде суммы n факторов, являющихся циклами. Если при 1-факторизации речь идёт о возможности разбиения множества рёбер на подмножества, состоящие из попарно несмежных рёбер (при этом каждое из подмножеств есть 1-фактор), то всякое разбиение множества вершин графа на n подмножеств таких, что вершины из любых двух разных подмножеств попарно несмежны, определяет правильную раскраску графа в n цветов. Теория раскрасок графа возникла и развивалась в связи с четырёх красок задачей, которая получила решение лишь на рубеже 1970-80-х годов.
С графом G = (V, Е) естественно связывается целый ряд графов, например его подграфы, дополнительный граф, рёберный граф L(G). Рёберным для графа G с р вершинами и q рёбрами называется граф с множеством вершин Е, в котором две вершины соединены ребром тогда и только тогда, когда соответствующие рёбра смежны в G. Критерий того, что данный граф является рёберным графом, заключается в отсутствии у него подграфов, принадлежащих множеству из 9 конкретно указанных графов (с 4, 5 или 6 вершинами). Изучение специальных классов графов, выделяемых каким-либо определяющим признаком или структурным свойством, составляет одно из направлений теории графов.
Если граф задан бинарным отношением на множестве, то часто возникает вопрос о том или ином его конкретном представлении. Такого рода задачей является задача о планарности графа, т. е. о возможности представить его на плоскости рисунком, в котором нет пересечения рёбер. Наиболее известный критерий планарности даёт теорема Понтрягина - Куратовского: граф является планарным тогда и только тогда, когда он не содержит в качестве подграфа ни полного графа К 5 , ни двудольного графа К 3,3 . Граф G = (V, Е) называется двудольным, если допускается разбиение вершин множества V на два подмножества V 1 и V 2 , состоящие из попарно несмежных вершин, такой граф обозначается K n1 , n2 , где n i - число вершин в подмножестве V i , i = 1, 2.
Значительная часть исследований в графов теории составляют перечислительные и экстремальные задачи. Отдельный класс экстремальных задач - задачи о покрытии. Основными объектами исследования в задачах о покрытии являются четыре важнейшие теоретико-графовые константы: число вершинного покрытия α 0 , число рёберного покрытия α 1 , вершинное число независимости β 0 и рёберное число независимости ß 1 . Число вершинного покрытия графа G есть минимальное число вершин в покрывающем множестве, т. е. в таком множестве вершин, для которого каждое ребро графа G инцидентно хотя бы одной вершине этого множества. Вершинное число независимости графа G есть наибольшее возможное число элементов в независимом множестве, т. е. в таком множестве вершин, в котором любые две вершины несмежны. Аналогично определяются число рёберного покрытия и рёберное число независимости. Для любого связного графа G с р > 1 вершинами α 0 + ß 0 = α 1 + ß 1 = р, а для двудольного графа ß 1 = α 0 . Значения этих констант известны лишь для некоторых графов частного вида. К задачам о покрытии тесно примыкает теория доминирования. В ней рассматриваются доминирующие множества графа G = (V, Е), то есть такие подмножества D с V, что любая вершина из VD смежна хотя бы с одной из вершин D. Важнейшей константой графа является число доминирования - наименьшее возможное число вершин в его доминирующем множестве.
Лит.: Кönig D. Theorie der endlichen und unendlichen Graphen. N. Y., 1950; Берж К. Теория графов и ее применение. М., 1962; Зыков А. А. Теория конечных графов. Новосиб., 1969; Харари Ф. Теория графов. М., 1973; Басакер Р., Саати Т. Конечные графы и сети. М., 1974; Камерон П., Линт Д. Теория графов, теория кодирования и блок-схемы. М., 1980; Оре О. Теория графов. 2-е изд. М., 1980; Цветкович Д., Дуб М., Закс Х. Спектры графов. Теория и применение. К., 1984; Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М., 2000; Колчин В. Ф. Случайные графы. 2-е изд. М., 2004; Сачков В. Н. Введение в комбинаторные методы дискретной математики. 2-е изд. М., 2004.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
Основные сферы применения теории графов:
В химии (для описания структур, путей сложных реакций, правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия - сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений;
В информатике и программировании (граф-схема алгоритма);
В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете;
В экономике;
В логистике;
В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).
Выделяют особый вид графа, дерево. Дерево - это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность - отсутствие циклов и то, что между парами вершин имеется только по одному пути. На Рис 1.3 представлено двоичное дерево .
Двоичное дерево - древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом , а дети называются левым и правым наследниками .
Матричное представление графов. Матрица инциденций.
Развитие алгоритмических подходов к анализу свойств графов требует определенных способов описания графов, более пригодных для практических вычислений, в том числе с использованием ЭВМ. Рассмотрим три наиболее распространенных способа представления графов.
Предположим, что все вершины и все ребра неориентированного графа или все вершины и все дуги (включая петли) ориентированного графа пронумерованы начиная с единицы. Граф (неориентированный или ориентированный) может быть представлен в виде матрицы типа , где- число вершин, а- число ребер (или дуг). Для неориентированного графа элементы этой матрицы задаются следующим образом:
Для ориентированного графа элементы матрицы задаются так:
Матрицу типа, определенную указанным образом, называютматрицей инциденций.
Пример получения матрицы инциденций. Для изображенного ниже графа (Рис. 2.1 а Рис 2.1 б).
Рис 2.1 а Рис. 2.1 б
Матрица смежности.
Несмотря на то, что представление графа в виде матрицы инциденций играет весьма большую роль в теоретических исследованиях, практически этот способ весьма неэффективен. Прежде всего, в матрице в каждом столбце только два ненулевых элемента, что делает этот способ представления графа неэкономным при большом количестве вершин. Кроме того, решение практических задач с помощью матрицы инциденций весьма трудоемко.
Оценим, например, временные затраты на решение с помощью матрицы инциденций такой простой задачи в ориентированном графе: для данной вершины найти ее "окружение" - множество преемников и множество предшественников вершины, т.е. множество всех вершин, непосредственно достижимых из, и множество всех вершин, из которых она непосредственно достижима.
Для решения этой задачи на матрице инциденций ориентированного графа нужно идти по строке с номером до появления ненулевого элемента (+1 или –1). В случае если обнаружена +1, в соответствующем столбце надо найти строку, в которой записано число –1. Номер строки, в которой стоит это число, дает номер вершины, непосредственно достижимой из данной вершины. Если обнаружена –1, в столбце надо найти строку, в которой записана 1, и получить номер вершины, из которой непосредственно достижима данная вершина. Для получения всего "окружения" надо проделать указанный поиск для всех ненулевых элементов k-й строки. Наиболее трудоемкой процедурой является поиск ненулевого элемента в столбце. Число таких процедур поиска равно степени вершины. Будем в этом случае говорить, что сложность алгоритма анализа окружения вершинысоставляет(порядка).
Можно увидеть, что поиск "окружения" всех вершин займет время порядка произведения числа вершин ориентированного графа на сумму степеней всех вершин, которая, как можно показать, пропорциональна числу дуг ориентированного графа. Таким образом, сложность алгоритма поиска "окружения" составляет , т.е. поиск занимает время порядка произведения числа вершин на число дуг.
Более эффективной матричной структурой, представляющей граф, служит матрица смежности вершин , или булева матрица графа. Это квадратная матрица В порядка n , элементы которой определяют следующим образом:
для
неориентированного графа:
для
ориентированного графа:
Для изображенного ниже графа (Рис. 2.2 а ) матрицей инциденций будет матрица, представленная на (Рис 2.2 б).
Теория графов - раздел математики, используемый в информатике и программировании, экономике, логистике, химии.
Что такое граф
Часто для описания строения систем используют графические схемы. Элементы в них изображают кружками, точками, квадратами и т. п., а связи между элементами - линиями или стрелками. При этом ни то, как изображаются элементы, ни длина или форма линий не важны - имеет значение только, какие элементы соединены. Итак, граф - это пара вида (A, M), где A - конечное множество вершин, а M - множество ребер - линий, связывающих некоторые вершины.
Основные понятия теории графов
У ориентированного графа или орграфа (см. рисунок ниже) ребра ориентированы, называются дугами и изображаются стрелками. Дуга может быть обозначена упорядоченной парой вершин, которые она связывает, - начальной и конечной.
У неориентированного графа (см. рисунок ниже) ребра изображаются линиями без ориентации. Соответственно, пара вершин, которую связывает ребро, является неупорядоченной. Обе эти вершины есть концы ребра.
Если вершины a и b - концы ребра (или начало и конец дуги) графа, то говорят, что вершины a и b инцидентны этому ребру (дуге), также ребро (дуга) инцидентно вершинам a и b. Если вершины a и b - концы ребра, то они (a и b) называются смежными.
Чаще всего рассматривают графы, ребра которых имеют один тип - являются ориентированными или нет.
Если ребра имеет одинаковые начало и конец, то их называют кратными ребрами, а граф, в котором они присутствуют, называется мультиграфом.
Теория графов также использует понятие «петля» - ребро, выходящее и заходящее в одну и ту же вершину. Граф, в котором есть петли, называется псевдографом.
Чаще всего встречаются неориентированные графы, у которых нет кратных ребер и нет петель. Такие графы называются обыкновенными. Они не имеют кратных ребер, поэтому можно отождествить ребро и соответствующую пару вершин.
Каждая вершина орграфа характеризуется:
- Полустепенью исхода. Это количество дуг, выходящих из нее.
- Полустепенью захода. Это количество дуг, которые входят в данную вершину.
Сумма полустепеней захода орграфа, а также сумма полустепеней исхода равны общему количеству дуг графа.
У неориентированного графа каждая вершина характеризуется степенью вершины. Так называется количество ребер, которые инцидентны вершине. Общая сумма степеней вершин графа есть количество ребер, умноженное на два: каждое ребро будет давать вклад, который равен двум.
Вершина со степенью 0 называется изолированной.
Висячей вершиной является вершина со степенью 1.
Теория графов называет пустым графом такой, в котором нет ни одного ребра. Полный граф - это обыкновенный граф, в котором смежны любые 2 вершины.
Взвешенные графы - это графы, вершинам или ребрам (дугам) которых или и вершинам, и ребрам (дугам) сразу, приписываются некоторые числа. Они называются весами. На втором рисунке показан неориентированный граф, ребра которого взвешены.
Графы: изоморфизм
Понятие изоморфизма используется в математике. В частности, теория графов определяет его так: два графа U и V изоморфны, если в этих графах существует биекция между множествами их вершин: каждые 2 вершины в графе U соединены ребром в том и только том случае, если в графе V связаны ребром те же вершины (которые могут по-другому называться). На рисунке ниже показаны два изоморфных графа, в которых между вершинами, окрашенными в одинаковые цвета и в первом, и во втором графе, существует вышеописанная биекция.
Пути и циклы
Путем в неориентированном или ориентированном графе является последовательность ребер, где каждое следующее начинается в вершине, в которой заканчивается предыдущее. Простой путь - такой, в котором все вершины, исключая, может быть, начальную и конечную, и ребра различны. Циклом в орграфе называется путь, у которого совпадают начальная и конечная вершины и который включает не менее одного ребра. Циклом в неориентированном графе является путь, который содержит не менее трех различных ребер. На втором рисунке циклом является, например, путь (3, 1), (6, 3), (1, 6).
Теория графов в программировании используется для построения граф-схем алгоритмов.
Назад
Вперёд
Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.
Цели урока:
Оборудование:
- компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
- компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
- оборудование доски (тема урока, новые термины). Раздаточный материал.
План урока.
II. Изложение нового материала. (10 мин.)
III. Закрепление материала. Практическая работа. (15-20 мин.)
IV. Подведение итога урока.(2 мин)
V. Домашнее задание.
I. Организационный момент. Актуализация знаний.
Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.
II Изложение нового материала.
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними. Это замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
Граф – это некоторая информационная модель
Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.
Примеры графов (Слайд 4, 5, 6)
Задание 1 (Слайд 7):
Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.
Можно ли долететь на рейсовых ракетах с Земли до Марса?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Две вершины, соединённые дугой или ребром называются смежными. Каждому ребру или дуге соотносится какое-нибудь число. Число может обозначать расстояние между населёнными пунктами, время перехода от одной вершины к другой и т. д.
Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?
Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?
Представление графов (Слайд 12)
Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.
| Списки дуг | Графическая форма | Табличная форма | ||||||||||||||||
| (АВ; 7), |  |
|
III. Закрепление материалы: учащимся предлагается разделить на группы и выполнить задания. Работая в малой группе, ученики обсуждают модели, основываясь на теоретических знаниях, полученных в начале урока. Тем самым достигается повторение и закрепление материала.
Задание 2 (Слайд 13)
IV. Итог урока
Ребята, какие новые слова вы сегодня узнали? (Граф, вершина графа, ребра графа.)
Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)
Что обозначают ребра графа (Пути, движения, направления)
Приведите пример, где в жизни мы можем с ними встретиться?
Как изображаются графы?
V. Домашнее задание. (Слайд 15)
Книга К.Бержа - первая по теории графов на русском языке. Между тем в последние годы интерес к теории резко усилился как со стороны математиков, так и представителей самых различных дисциплин. Это объясняется тем, что методы теории графов успешно решают многочисленные задачи теории электрических цепей, теории транспортных цепей, теории информации, кибернетики и др.
В книге Бержа теория графов излагается последовательно, начиная с самых основ. Предполагается, что читатель обладает весьма скромными математическими познаниями, хотя и имеет некоторую математическую культуру. В текст включены многочисленные, зачастую забавные, примеры. Книга может быть использована для первоначального изучения теории графов. Математики-профессионалы также найдут в ней много интересного.
Алгорифм для непосредственного выявления эйлерова цикла.
[Флёрн (Fleury)]. Рассмотрим связный мультиграф G, все вершины которого имеют четную степень, и постараемся нарисовать его одним росчерком, не прибегая в процессе построения к исправлениям уже начерченной части траектории. Достаточно придерживаться следующего правила:
1 Выходим из произвольной вершины а; каждое пройденное ребро зачеркиваем.
2 Никогда не идем по такому ребру и, которое в рассматриваемый момент является перешейком (т.е. при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру),
Соблюдая это правило, мы всегда будем находиться в благоприятном положении, потому что когда мы находимся в х = а, граф (из незачеркнутых ребер) имеет две вершины нечетной степени: х и а; если отбросить изолированные вершины, то останется связный граф, который в силу теоремы 1 имеет эйлерову цепь, начинающуюся в х.
Содержание
Введение
Глава 1. Основные определения
Множества и многозначные отображения
Граф. Пути и контуры
Цепи и циклы
Глава 2. Предварительное изучение квазиупорядоченности
Квазипорядок, определяемый графом
Индуктивный граф и базы
Глава 3. Порядковая функция и функция
Гранди для бесконечного графа
Общие соображения относительно бесконечных графов
Порядковая функция
Функции Гранди
Операции над графами
Глава 4. Основные числа теории графов
Цикломатическое число
Хроматическое число
Число внутренней устойчивости
Число внешней устойчивости
Глава 5. Ядра графа
Теоремы существования и единственности
Приложение к функциям Гранди
Глава 6. Игры на графе
Игра Ним
Общее определение игры (с полной информацией)
Стратегии
Глава 7. Задача о кратчайшем пути
Процессы по этапам Некоторые обобщения
Глава 8. Транспортные сети
Задача о наибольшем потоке Задача о наименьшем потоке
Задача о потоке, совместимом с множеством значений
Бесконечные транспортные сети
Глава 9. Теорема о полустепенях
Полу степени исхода и захода
Глава 10. Паросочетание простого графа
Задача о наибольшем паросочетании
Дефицит простого графа
Венгерский алгорифм
Обобщение на бесконечный случай
Приложение к теории матриц
Глава 11. Факторы
Гамильтоновы пути и гамильтоновы контуры
Нахождение фактора
Нахождение частичного графа с заданными полустепенями
Глава 12. Центры графа
Центры
Радиус
Глава 13. Диаметр сильно связного графа
Общие свойства сильно связных графов без петель
Диаметр
Глава 14. Матрица смежности графа
Применение обычных матричных операций
Задачи на подсчет
Задача о лидере
Применение булевых операций
Глава 15. Матрицы инциденций
Вполне унимодулярные матрицы
Вполне унимодулярные системы
Цикломатические матрицы
Глава 16. Деревья и прадеревья
Деревья
Аналитическое исследование
Прадеревья
Глава 17. Задача Эйлера
Эйлеровы циклы Эйлеровы контуры
Глава 18. Паросочетание произвольного графа
Теория чередующихся цепей
Нахождение частичного графа с заданными степенями вершин
Совершенное паросочетание
Приложение к числу внутренней устойчивости
Глава 19. Фактороиды
Гамильтоновы циклы и фактороиды
Необходимое и достаточное условие существования фактороида
Глава 20. Связность графа
Точки сочленения
Графы без сочленений
h-связные графы
Глава 21. Плоские графы
Основные свойства
Обобщение
Добавления
I. Off общей теории, игр
II. О транспортных задачах
III. Об использовании, понятия потенциала в транспортных сетях
IV. Нерешенные задачи, и недоказанные предположения
V. О некоторых основных принципах подсчета (Ж. Риге)
VI. Дополнения к русскому переводу (А.А. Зыков и Г.И. Кожухин)
Литература
Теория графов и книга К. Бержа (послесловие к русскому переводу)
Указатель символов
Именной указатель
Предметный указатель.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория графов и её применение, Берж К. - fileskachat.com, быстрое и бесплатное скачивание.
