Контрольная работа код харари. _Харари_Ф._Теория_графов__1973. Теория графов Харари теория графов pdf читать

Я не люблю цитат. Скажи, что знаешь сам.
Р.Эмерсон (1803--1882) -- американский писатель и философ.

Прошло 30 лет после выпуска монографии Ф.Харари "Теория графов", но ее привлекательные качества нисколько не потускнели. Унификация терминологии, проведенной автором и широко распространенной благодаря этой книге, стала общепринятой. Преподавание теории графов с использованием книги Ф.Харари ведется во многих вузах нашей страны. За прошедшее время значительно расширилась сфера применения теории графов -- при построении больших вычислительных систем и в программировании, в экономике и на транспорте, в генетике и биологии и т.д. Продолжается значительный рост публикаций, вышел в свет ряд учебных пособий и монографий, среди которых можно отметить книги А.А.Зыкова "Элементы теории графов" (М.: Наука, 1987) и В.А.Емеличева и др. "Лекции по теории графов" (М.: Наука, 1990).

Большое число задач, указанных в книге как нерешенные, нашли свое решение, и часть из них была решена многочисленными учениками Ф.Харари. Сам Ф.Харари, которому сейчас более 80 лет, плодотворно работает и публикуется до сих пор. Особенно значительные успехи за прошедшее время были получены по построению эффективных алгоритмов решения задач теории графов, среди которых нужно отметить алгоритмы построения максимального потока (см.: Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. М.: Наука, 1975). И это несмотря на то, что многие задачи теории графов -- нахождение минимальных раскрасок, покрытий, максимальных полных подграфов, гамильтоновых циклов и др., -- являются NP-полными, т.е. алгоритмически сложными (см.: Гэри М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи. М.: Мир, 1982). Недостаточную оснащенность книги Ф.Харари алгоритмами частично компенсирует книга Н.Кристофидеса "Теория графов. Алгоритмический подход" (М.: Мир, 1978). Обзор результатов по теории графов можно найти в работах: Козырев В.П. Теория графов // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1972. Т. 10. С.25--74; Козырев В.П., Юшманов С.В. Теория графов (алгоритмические, алгебраические и метрические проблемы) // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1985. Т. 23. С.68--117; Козырев В.П., Юшманов С.В. Представление графов и сетей (кодирование, размещения и укладки) // Итоги науки и техники. ВИНИТИ, сер. теор. вероятн., мат. стат. и теор. киберн. 1990. Т. 27. С.129--196.

В.П.Козырев

Когда мне было 14 лет, мой отец был так глуп, что я едва выносил его. Когда же мне стукнуло 21, я поразился, увидев, как поумнел старик за эти 7 лет.
Марк Твен

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

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

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

Предлагаемые в конце каждой главы (кроме первой) упражнения существенно отличаются друг от друга по своей трудности. Номера тех упражнений, которые не являются простыми и не следуют непосредственно из приводимых ранее результатов, набраны жирным шрифтом. Особенно трудные упражнения кроме того помечены звездочкой. Для усвоения излагаемого в книге материала читателю рекомендуется ознакомиться с каждым упражнением. Многие из "более легких" упражнений могут показаться читателю очень трудными, если он не изучил материал соответствующих глав.

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

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

В течение последнего года мои ученики Деннис Геллер, Беннет Манвел и Поль Штокмейер с особым энтузиазмом делились своими замечаниями и предложениями. Большая помощь была также оказана мне Стефаном Хедетниеми, Эдгаром Палмером и Майклом Пламмером. В самое последнее время Бранко Грюнбаум и Доминик Уэлш оказали любезность, тщательно прочитав всю книгу. Я лично отвечаю за все ошибки и за большинство сомнительных мест в изложении.

За последние более чем двадцать лет, посвященных исследованиям в теории графов, я получал поддержку при публикации со стороны Научно-исследовательского управления Военно-воздушных сил США, Национальных институтов здоровья, Национального научного фонда, Управления научных разработок Военно-морского флота и фонда Рокфеллера. В течение этого времени я был рад воспользоваться гостеприимством не только Мичиганского университета, но также и других учебных заведений, которые я имел возможность посетить. Среди них -- Институт повышения квалификации, Принстонский университет, Тавистокский институт социологии в Лондоне, Университетский колледж в Лондоне и Лондонская экономическая школа. Квалифицированно и быстро перепечатали рукопись Алиса Миллер и Анна Дженн из Научно-исследовательского центра групповой динамики. Наконец, я особенно благодарен издательству Аддисон-Уэсли за проявленное терпение в ожидании этой рукописи в течение всех десяти лет с момента заключения контракта, а также за всестороннюю помощь в издании книги.

Фрэнк Харари

Харари Фрэнк (Frank Harary)

Выдающийся американский математик, специалист в области дискретной математики. Родился в Нью-Йорке, в семье еврейских эмигрантов с Ближнего Востока. Окончил Бруклинский колледж, получив степень бакалавра в 1941 г. и магистра в 1945 г. В 1948 г. получил степень доктора философии Калифорнийского университета в Беркли. С 1948 по 1985 гг. занимал должность профессора Мичиганского университета. С 1987 г. - экстраординарный (впоследствии почетный) профессор университета в Лас-Крусес (штат Нью-Мексико).

Фрэнк Харари - автор многочисленных научных работ, книг и статей по теории графов и ее применениям в различных областях знания, особенно в области социальных наук, в том числе лингвистики, социологии, политологии, психологии и др. С лекциями по теории графов он выступал более чем на тысяче научных конференций в 87 странах. Многие его ученики, среди которых 16 докторов наук, стали выдающимися учеными. Он был основателем и членом редакционных коллегий нескольких научных журналов, посвященных дискретной математике, был удостоен почетных ученых степеней в американских и европейских университетах. Его классическая работа «Теория графов» (1969) стала настольной книгой для всех специалистов этого раздела математики.

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

Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"

Подобные документы

История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.

курсовая работа , добавлен 20.12.2015


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

курсовая работа , добавлен 23.12.2007


Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.

дипломная работа , добавлен 05.06.2014


Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".

курсовая работа , добавлен 08.10.2014


Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.

курсовая работа , добавлен 30.09.2014


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

дипломная работа , добавлен 19.07.2011


Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.

презентация , добавлен 19.11.2013

ТЕОРИЯ ГРАФОВ

М.: Мир, 1973, 300 стр.

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

За последние годы тематика теории графов стала значительно разнообразней; резко увеличилось количество публикаций.

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

Тороидальный 142

Тотальный 103

- точек сочленения 45

Тривиальный 22

Хивуда 204

Эйлеров 83

- n-раскрашиваемый 152

N-транзитивный 204

- n-унитранзитивный 204

N-хроматический 152

- \alpha-перестановочный 206 граф-композиция 196 графоид 58 графы гомеоморфные 132

Изоморфные 24, 190

- коспектральные 188 группа 189

Графа 190

Вершинная 190

Диэдральная 195

- знакопеременная 195

Конфигураций 213

Парная 217

- - редуцированная 218

Подстановок 190

Реберная 191

- симметрическая 195

Степенная 194

- тождественная 195

Циклическая 195

группы идентичные 190

- изоморфные 190 дерево 48

- блоков и точек сочленения 54

Корневое 219

- с висячим корнем 220

Входящее 235

Выходящее 235

диагональ блока 47 «диаграмма Хассе» 73 диаметр 27 длина маршрута 27

добавление вершины 25 - ребра 25

дополнение графа 29 достижимость 133 древесность графа 113

дуга 23, 232

животное 227 замощение решетки, 2, 227 звезда (лапа, гроздь) 32 изоморфизм 24 инвариант 24

инцидентность ребра и вершины 22 искаженность графа 149 источник 235 карта плоская 127

- - с корневым ребром 227 квадрат графа 27 квадратный корень графа 38 клетка 204 количество очков 243 клика графа 34 кограница 55

кограничный оператор 54 кодерево 56 колесо 63 комплекс 20

композиция графов 37, 196

Групп 194

компонента 27

Нечетная 108

- односторонняя 233

Сильная 233

- слабая 233 конденсация 234 контур 233

- эйлеров 240 конфигурация 213 конъюнкция 40, 243 корона графов 198 коцикл 55 крупность (зернистость,

шероховатость) 146 лемма Бернсайда 212, 214 лес 48 линия матрицы 71

линейный подграф графа 180

- - орграфа 179 Маршрут 26

Замкнутый 26

- несовершенный 119

Открытый 26

Совершенный 119

Y-сводимый 120

матрица достижимостей 238

Инциденций ISO

Коциклов 184

Обходов 238

- полустепеней захода 239

Исхода 239

Разреженная 241

- смежностей графа 179

Орграфа 237

Циклов 183

матричная теорема о деревьях 178, 181, 239

матроид 57

Бинарный 188

Графический 180

- кографический 180

- коциклов графа 57

Циклов графа 57

Эйлеров 188

многочлен деревьев графа 187 множество вершин 22

- внешне устойчивое 118

- внутренне устойчивое 118

- независимое 57, 108, 118

Разделяющее 64

Ребер 22

мост 41 мультиграф 23

наследственное свойство 119 надграф 24 независимые единицы матрицы 71 обхват 27 объединение графов 36 одноцветный класс 152

ожерелье 212-215, 224, 225

окрестность вершины 197 - замкнутая 197

окружение 27 орбита 211 орграф 232

Бесконтурный 235

- контрафункциональный 236 орграф несвязный 233

Обратный 234

- односторонний 233

Примитивный 246

Реберный 245

Сильный 233

Слабый 233

- строго односторонний 244

Слабый 244

- функциональный 236

Эйлеров 240

ориентация графа 246 остов 55 пара связностей 62

паросочетание 119

- наибольшее 119 перечисляющий ряд для

конфигураций 213

Фигур 213

петля 23 подграф 24

ранг коциклический 56

- циклический 55 размерность симплекса 20 расстояние в графе 27

Орграфе 233

раскраска графа 152

Плоской карты 156

Полная 170

Ребер 159

- t цветами 172 ребра кратные 23

Независимые 108

Подобные 01, 2

- смежные 22 ребро графа 22

- инцидентное вершине 22

Критическое 121

Подразбитое 101

Симметричное 221

род графа 142

- полиэдра 142 сеть 70

система различных представителей

стабилизатор 211 степень вершины 27

Графа 27

Группы 190

Ребра 202

сток 235 стягивание 137

- элементарное 137 сумма графов 37

Групп 193

теорема Вине-Коши 181

- об интерполяции гомоморфизмов

- о пяти красках 151, 155, 156

- перечисления Пойа 211-215, 217, 218

- - степенной группы 224

- Хивуда о раскраске Карт 162-164

BEST 240

толщина графа 145 точка сочленения 41 транзитивная тройка 241 треугольник 26

Нечетный 95

- четный 95 турнир 241

турнир состязаний 245 тэта-граф 85 удаление вершины 25

Ребра 25

укладка графа 126 уравнение характеристики неподобия

для деревьев 221

Эйлера-Пуанкаре 57 фактор графа 106 факторизация графа 106 фигура 213 формула Оттера 222

- Эйлера для полиэдров 127 функция связности 62 связность 60

Локальная 66

- односторонняя 233

Реберная 60

Сильная 233

Слабая 233

хорда 55 хроматический класс 159 - многочлен 173

цветной граф группы 199 центр графа 51

, 2-Лек_Ықтималдылықтар теориясы.doc .

Ф.Харари
ТЕОРИЯ ГРАФОВ
М.: Мир, 1973, 300 стр.
В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких пауках , как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от нее, - экономику, социологию, лингвистику и др. Давно известии тесные контакты теории графов с топологией, теорией групп и теорией вероятностей. Особенно важная взаимосвязь существует между теорией графов и теоретической кибернетикой (особенно теорией автоматов, исследованием операций, теорией кодирования, теорией игр).
Широко используется теория графов при решении различных задач на вычислительных машинах.
За последние годы тематика теории графов стала значительно разнообразней ; резко увеличилось количество публикаций.
Предлагаемая книга написана одним из видных специалистов по дискретной математике. Несмотря на небольшой объем и конспективный характер изложения, книга достаточно полно освещает современное состояние теории графов. Она, безусловно, будет полезна студентам университетов и технических вузов и, несомненно, заинтересует широкие круги научных работников, занимающихся приложениями дискретной математики.
Предисловие редактора перевода 6
Введение 9
Глава 1. Открытие! 13
Задача о кёнигсбергских мостах 13
Электрические цепи 14
Химические изомеры 15
«Вокруг света» 16
Гипотеза четырех красок 17
Теория графов в двадцатом веке 18
Глава 2. Графы 21
Типы графов 21
Маршруты и связность 26
Степени 27
Задача Рамсея 28
Экстремальные графы 30
Графы пересечений 33
Операции над графами 35
Упражнения 38
Глава 3. Блоки 41
Точки сочленения, мосты и блоки 41
Графы блоков и графы точек сочленения 45
Упражнения 46

Глава 4. Деревья 48
Описание деревьев 48
Центры и центроиды 51
Деревья блоков и точек сочленения 53
Независимые циклы и коциклы 54
Матроиды 57
Упражнения 59
Глава 5. Связность 60
Связность и реберная связность 60
Графические варианты теоремы Менгера 64
Другие варианты теоремы Менгера 70
Упражнения 74
Глава 6. Разбиения 76
Упражнения 81
Глава 7. Обходы графов 83
Эйлеровы графы 83
Гамильтоновы графы 85
Упражнения 88
Глава 8. Реберные графы 91
Некоторые свойства реберных графов 91
Характеризация реберных графов 94
Специальные реберные графы 99
Реберные графы и обходы 101
Тотальные графы 103
Упражнения 104
Глава 9. Факторизация 106 1-факторизация 106 2-факторизация 111
Древесность
113
Упражнения 116
Глава 10. Покрытия 117
Покрытия и независимость 117
Критические вершины и ребра 120
Реберное ядро 122
Упражнения 124
Глава 11. Планарность
126
Плоские и планарные графы 126
Внешнепланарные графы 131
Теорема Понтрягина - Куратовского 133
Другие характеризации пленарных графов 138
Род, толщина, крупность, число скрещиваний 141
Упражнения 148
Глава 12. Раскраски 151
Хроматическое число 152

Теорема о пяти красках 155
Гипотеза четырех красок 156
Теорема Хивуда о раскраске карт 162
Однозначно раскрашиваемые графы 164
Критические графы 167
Гомоморфизмы 169
Хроматический многочлен 172
Упражнения 175
Глава 13. Матрицы 178
Матрица смежностей 178
Матрица инциденций 180
Матрица циклов 183
Обзор дополнительных свойств матроидов 186
Упражнения 187
Глава 14. Группы 189
Группа автоморфизмов графа 193
Операции на группах подстановок 194
Группа графа-композиции 195
Графы с данной группой 198
Симметрические графы 201
Графы с более сильной симметрией 204
Упражнения 206
Глава 15. Перечисления 209
Помеченные графы 209
Теорема перечисления Пойа 211
Перечисление графов 216
Перечисление деревьев 219
Теорема перечисления степенной группы 224
Решенные и нерешенные задачи перечисления графов 225
Упражнения 230
Глава 16. Орграфы 232
Орграфы и соединимость 232
Ориентированная двойственность и бесконтурные орграфы 234
Орграфы и матрицы 237
Обзор по проблеме восстановления турниров 244
Упражнения 244
Приложение I. Диаграммы графов 248
Приложение II. Диаграммы орграфов 260
Приложение III. Диаграммы деревьев 266
Список литературы и именной указатель 268
Указатель обозначений 291
Предметный указатель 293
Предметный указатель автоморфизм графа 190 базис коциклов 55

Циклов 55 блок 41 валентность вершины 27 вершина графа 22, 126
- изолированная 28
- инцидентная ребру 22
- концевая 28
- критическая 121
- неподвижная 201
- орграфа 232
- периферическая 51
- центральная 51
- центроидная 52 вершинная база 237 вершины подобные 201
- смежные 22, 213 вес вершины 52 вес функции 213 ветвь 56
- к вершине 52 вихрь 187 внешность цикла 134 выпуклый полиэдр 130 гипотеза Улама 25, 26, 48, 58, 202,
244
- Хадвигера 161, 162
- четырех красок 151, 156-162, 164,
167, 172 гомоморфизм графа 169
- полный порядка л 169
- элементарный 169 гомоморфный образ графа 196 граничный оператор 54 грань 127
- внешняя 127
- внутренняя 127 граф асимметрический 190
- ациклический 48
- базисный 132
- бесконечный 36
- блоков 45
- - и точек сочленения 53
- вершинно-критический 121
- вершинно-симметрический 201
- внешнепланарный 131
- - максимальный 131
- вполне несвязный 28
- гамильтонов 85
- геометрически двойственный 138
- Давида 29
- двудольный 31
- дополнительный 29
- интервалов 35
- клик 34
- комбинаторно двойственный 139
- критический 167
- кубический 28
- Леви 205, 206
- Мак-Джи 205
- направленный 23
- неразделимый 41
- несводимый 123
- однозначно раскрашиваемый 164
- одноциклический 58
- пересечений 33
- Петерсена 113
- планарный 127
- - максимальный 128
- плоский 127
- подразбиений 101
- полный 29 граф полный двудольный 32
- - n-дольный 37
- полунесводимый 123
- помеченный 23
- произвольно гамильтонов 89
- - проходимый 89
- простой 197
- реберно-критический 121
- реберно-регулярный 202
- реберно-симметрический 201
- реберный 91, 94
- - итерированный 91
- регулярный 28
- самодополнительный 29
- сводимый 123
- симметрический 201
- составной 197

Тороидальный 142
- тотальный 103
- точек сочленения 45
- тривиальный 22
- Хивуда 204
- эйлеров 83
- n-раскрашиваемый 152
- n-транзитивный 204
- n-унитранзитивный 204
- n-хроматический 152
- \alpha-перестановочный 206 граф-композиция 196 графоид 58 графы гомеоморфные 132
- изоморфные 24, 190
- коспектральные 188 группа 189
- графа 190
- вершинная 190
- диэдральная 195
- знакопеременная 195
- конфигураций 213
- парная 217
- - редуцированная 218
- подстановок 190
- реберная 191
- симметрическая 195
- степенная 194
- тождественная 195
- циклическая 195 группы идентичные 190
- изоморфные 190 дерево 48
- блоков и точек сочленения 54
- корневое 219
- с висячим корнем 220
- входящее 235
- выходящее 235 диагональ блока 47
«диаграмма Хассе» 73 диаметр 27 длина маршрута 27 добавление вершины 25
- ребра 25 дополнение графа 29 достижимость 133 древесность графа 113 дуга 23, 232 животное 227 замощение решетки, 2, 227 звезда (лапа, гроздь) 32 изоморфизм 24 инвариант 24 инцидентность ребра и вершины 22 искаженность графа 149 источник 235 карта плоская 127
- - с корневым ребром 227 квадрат графа 27 квадратный корень графа 38 клетка 204 количество очков 243 клика графа 34 кограница 55 кограничный оператор 54 кодерево 56 колесо 63 комплекс 20 композиция графов 37, 196
- групп 194 компонента 27
- нечетная 108
- односторонняя 233
- сильная 233
- слабая 233 конденсация 234 контур 233
- эйлеров 240 конфигурация 213 конъюнкция 40, 243 корона графов 198 коцикл 55 крупность (зернистость, шероховатость) 146 лемма Бернсайда 212, 214 лес 48 линия матрицы 71 линейный подграф графа 180

Орграфа 179
Маршрут 26
- замкнутый 26
- несовершенный 119
- открытый 26
- совершенный 119
- Y-сводимый 120 матрица достижимостей 238
- инциденций ISO
- коциклов 184
- обходов 238
- полустепеней захода 239
- - исхода 239
- разреженная 241
- смежностей графа 179
- - орграфа 237
- циклов 183 матричная теорема о деревьях 178,
181, 239 матроид 57
- бинарный 188
- графический 180
- кографический 180
- коциклов графа 57
- циклов графа 57
- эйлеров 188 многочлен деревьев графа 187 множество вершин 22
- внешне устойчивое 118
- внутренне устойчивое 118
- независимое 57, 108, 118
- разделяющее 64
- ребер 22 мост 41 мультиграф 23 наследственное свойство 119 надграф 24 независимые единицы матрицы 71 обхват 27 объединение графов 36 одноцветный класс 152 ожерелье 212-215, 224, 225 окрестность вершины 197
- замкнутая 197 окружение 27 орбита 211 орграф 232
- бесконтурный 235
- контрафункциональный 236 орграф несвязный 233
- обратный 234
- односторонний 233
- примитивный 246
- реберный 245
- сильный 233
- слабый 233
- строго односторонний 244
- - слабый 244
- функциональный 236
- эйлеров 240 ориентация графа 246 остов 55 пара связностей 62 паросочетание 119
- наибольшее 119 перечисляющий ряд для конфигураций 213
- - - фигур 213 петля 23 подграф 24
- линейный 180
- остовный 24
- порожденный 24
- четный 227 покрытие вершинное 117
- реберное 117 полиэдр 127 полная раскраска 170 полный набор инвариантов 24 полугруппа графа 208 полуконтур 233 полумаршрут 233 полупуть 233 полустепень захода 232
- исхода 232 порядок группы 190 последователь n-пути 204

принцип ориентированной двойственности 234, 235 произведение графов 36
- групп 190
- поэлементное 239 пространство коциклов 55
- циклов 55 псевдограф 23 путь 233 разбиение графа 76
- графическое 76
- числа 76 разрез 55 ранг коциклический 56
- циклический 55 размерность симплекса 20 расстояние в графе 27
- - орграфе 233 раскраска графа 152
- плоской карты 156
- полная 170
- ребер 159
- t цветами 172 ребра кратные 23
- независимые 108
- подобные 01, 2
- смежные 22 ребро графа 22
- инцидентное вершине 22
- критическое 121
- подразбитое 101
- симметричное 221 род графа 142
- полиэдра 142 сеть 70 система различных представителей
72 стабилизатор 211 степень вершины 27
- графа 27
- группы 190
- ребра 202 сток 235 стягивание 137
- элементарное 137 сумма графов 37
- групп 193 теорема Вине-Коши 181
- об интерполяции гомоморфизмов
171
- о пяти красках 151, 155, 156
- перечисления Пойа 211-215, 217,
218
- - степенной группы 224
- Хивуда о раскраске Карт 162-164
- BEST 240 толщина графа 145 точка сочленения 41 транзитивная тройка 241 треугольник 26
- нечетный 95
- четный 95 турнир 241 турнир состязаний 245 тэта-граф 85 удаление вершины 25
- ребра 25 укладка графа 126 уравнение характеристики неподобия для деревьев 221
- Эйлера-Пуанкаре 57 фактор графа 106 факторизация графа 106 фигура 213 формула Оттера 222
- Эйлера для полиэдров 127 функция связности 62 связность 60
- локальная 66
- односторонняя 233
- реберная 60
- сильная 233
- слабая 233 хорда 55 хроматический класс 159
- многочлен 173 цветной граф группы 199 центр графа 51

центроид дерева 52 цепи непересекающиеся 64
- реберно-непересекающиеся 64 цепь 26
- альтернирующая 109
- геодезическая 27
- простая 26 цикл 26
- гамильтонов 85
- графой да 58
- матроида 57
- простой 26
- эйлеров 83 циклическая тройка 241 циклический вектор графа 54 цикловой индекс группы 212 число ахроматическое 170
- независимости вершинное 118
- - реберное 118
- пересечения 33
- покрытия вершинного 117
- - реберного 117
- Рамсея 30
- - реберное 104
- скрещиваний 148
- Хадвигера 177
- хроматическое 152
- n-хроматическое 177 экспоненцирование 208 эксцентриситет 51 элемент графа 103 элементы соседние 103 эндоморфизм графа 208 ядро вершинное 125
- реберное 122 цепь, 54 база, 1, 237 скелет, 1, 127 цепь, 1, 54 решетка, 2, 227 решетка, 3, 227 n-клетка 204 n-компонента 63 n-куб 37 n-путь 204 n-раскраска 152
- реберная 159 n-связность 63 n-фактор 106 n-факторизация 106
Р-множество 119