Название:

Размер: 1,73 Мб

Описание: О. Оре Графы и их применение Перевод с английского Л. И. Головиной Под редакцией И. М. Яглома Издательство «МИР» Москва 1965 Скачать бесплатно

Ссылка для скачивания файла:

 

 

 

 

Оглавление
От редактора 5
Введение 9
ГЛАВА I. Что такое граф? 11
§ 1. Спортивные состязания 11
§ 2. Нуль-граф и полный граф 13
§ 3. Изоморфные графы 15
§ 4. Плоские графы 19
§ 5. Одна задача о плоских графах 21
§ 6. Число ребер графа 26
ГЛАВА II. Связные графы 30
§ 1. Компоненты 30
§ 2. Задача о кенигсбергских мостах .... 32
§ 3. Эйлеровы графы 31
§ 4. Отыскание правильного пути 38
§ 5. Гамильтоновы линии 4
§ 6. Головоломки и графы 43
ГЛАВА III. Деревья 47
§ 1. Деревья и леса 47
§ 2. Циклы и деревья 49
§ 3. Задача о соединении городов 52
§ 4. Улицы и площади 55
Г Л А В А IV. Установление соответствий 59
§ 1. Задача о назначении на должности . . 59
§ 2. Другие формулировки 63
§ 3. Круговые соответствия 67
ГЛАВА V. Ориентированные графы 72
§ 1. Снова спортивные состязания 72
§ 2. Одностороннее движение 74
§ 3. Степени вершин . 81
§ 4. Генеалогические графы 83
ГЛАВА VI. Игры и головоломки 91
§ 1. Головоломки и ориентированные графы 91
§ 2. Теория игр 94
§ 3. Парадокс спортивных обозревателей . . 102
ГЛАВА VII. Отношения 108
§ 1. Отношения и графы 108
§ 2. Специальные условия 111
§ 3. Отношения эквивалентности 116
§ 4. Частичная упорядоченность 121
ГЛАВА VIII. Плоские графы 127
§ 1. Условия для плоских графов 127
§ 2. Формула Эйлера 131
§ 3. Некоторые соотношения для графов. Двойственные графы 135
§ 4. Правильные многогранники 138
§ 5. Мозаики 143
ГЛАВА IX. Раскрашивание карт 146
§ 1. Проблема четырех красок 146
§ 2. Теорема о пяти красках 150
Решения упражнений 156
Литература 166
Словарь основных терминов, используемых в книге  . 168

 

Словарь основных терминов, используемых в книге.
Ациклический граф. Ориентированный граф, не содержащий никакого ориентированного цикла.
Вершина графа. Либо конец какого-нибудь ребра графа, либо изолированная точка графа.
Гамильтонова линия. Элементарный цикл, проходящий по всем вершинам графа.
Грань многоугольного графа G. Часть плоскости, ограниченная каким-нибудь минимальным циклом из С или максимальным циклом С\ графа G; в последнем случае это часть плоскости, лежащая вне С\\ ее называют также бесконечной гранью.
Граф. Фигура, состоящая из точек (называемых вершинами) и отрезков, соединяющих некоторые из этих вершин.
Соединяющие отрезки могут быть прямолинейными или криволинейными; они называются ребрами графа.
Граф G*. двойственный многоугольному графу G.
Многоугольный граф, каждая вершина которого соответствует определенной грани графа С, а каждая грань — определенной вершине графа С. Две вершины графа G* соединены ребром в том и только в том случае, когда соответствующие грани графа G имеют общее ребро.
Двудольный граф. Граф, вершины которого можно разделить на два непересекающихся множества так, что вершины одного и того же множества не соединены между собой ребрами.
Дерево. Связный граф, не имеющий циклов.
Додекаэдр. Многогранник, ограниченный 12 пятиугольными гранями.
Дополнение G графа О. Граф G состоит из всех ребер (и их концов), которые необходимо добавить к G для того, чтобы получился полный граф.
Изолированная вершина. Вершина, из которой не исходит из одного ребра.
Изоморфные графы. Графы G\ и Gt изоморфны, если между их вершинами можно установить такое взаимно однозначное соответствие, что пары вершин графа G в том и только в том случае соединены ребром, когда соединены ребром соответствующие пары вершин графа Gj. В случае ориентированных графов это соответствие должно сохранять ориентацию ребер.
Икосаэдр. Многогранник, ограниченный 20 треугольными гранями.
Инцидентность ребра и вершины. Ребро называется инцидентным вершине, если она является одним из его концов.
Корень дерева. Любая вершина, которую мы выбираем за начальную точку дерева.
Кратные ребра. Если две вершины графа соединены более чем одним ребром, то каждое такое ребро называется кратным.
Лес. Граф, все связные компоненты которого являются деревьями (граф без циклов).
Максимальный цикл С: многоугольного графа G. Цикл, окружающий весь граф G.
Минимальный цикл многоугольного графа С. Цикл, образованный граничными ребрами одного из многоугольников, составляющих С.
Многогранник. Трехмерное тело, граница которого состоит из плоских многоугольников.
Многоугольный граф (многоугольная сеть). Плоский граф, ребра которого образуют множество смежных, не налегающих друг на друга многоугольников.
Нечетная вершина. Вершина, степень которой нечетна.
Нуль-граф. Граф, состоящий только из изолированных вершин: граф, не имеющий ребер.
Обратный граф G* для данного ориентированного графа G.
Граф G* получается из G изменением направлений всех его ребер.
Однородный граф степени г. Граф, степени всех вершин которого одинаковы и равны г. (В случае ориентированных графов требуется, чтобы степени р и р * были одинаковы во всех вершинах и равны друг другу.)
Октаэдр. Многогранник, ограниченный восемью треугольными гранями.
Ориентированный граф. Граф, на котором указаны направления всех его ребер.
Перешеек. Другой термин для связывающего ребра.

Петля. Ребро графа, оба конца которого совпадают.
Плоский граф. Граф, который можно начертить на плоскости так, чтобы его ребра пересекались только в его вершинах.
Полный граф. Граф, любые две вершины которого соединены ребром. Полный граф, у которого n вершин, имеет у n (n — 1) ребер.
Правильный граф. Многоугольный однородный граф, такой, что двойственный к нему граф G* тоже является однородным.
Правильный многогранник. Многогранник, все грани которого являются равными правильными многоугольниками и в каждой вершине которого сходится одно и то же число ребер.
Ребро графа. Кривая, соединяющая две вершины графа и не содержащая других вершин.
Связная компонента вершины А. Все вершины графа, которые можно соединить с точкой А цепями, и все инцидентные им ребра.
Связный граф. Граф, каждая вершина которого может быть соединена некоторой цепью с любой другой его вершиной.
Связывающее ребро. Ребро, удаление которого приводит к увеличению числа связных компонент графа.
Смешанный граф. Граф, на котором имеются как ориентированные, так и неориентированные ребра.
Степень р(А) вершины А. Число ребер, сходящихся в вершине А. Для ориентированного графа р(А) означает число выходящих ребер, а р*(-4)— число входящих ребер в вершине А; в этом случае имеются две степени.
Тетраэдр. Многогранник, ограниченный четырьмя треугольными гранями.
Цепь. Линия на графе, не проходящая ни по какому ребру более одного раза.
Цикл. Замкнутая цепь.
Циклическое ребро. Ребро, не являющееся связывающим.
Цикломатическое число графа G. Число ребер графа G минус число его вершин плюс единица.
Четная вершина. Вершина, степень которой четна.
Эйлеров граф. Граф, содержащий эйлерову линию.
Эйлерова линия. Цепь, проходящая по всем ребрам графа в точности по одному разу.
Элементарная цепь. Цепь, не проходящая ни через одну из своих вершин более одного раза.
Элементарный цикл. Цикл, ие проходящий ни через одну из своих вершин более одного раза.

 

 

 

Книги в бумажном виде. Дискретная математика в Интернет-магазине:

 

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