Елементи теорії графіків - PDF скачати безкоштовно
Елементи теорії графів
Спрингер Париж Берлін Гейдельберг Нью-Йорк Гонконг Лондон Мілан Токіо
Ален Бретто, Ален Фейсан, Франсуа Хеннекарт Елементи теорії графів
x Елементи теорії графів В останньому розділі не використовуються дуже глибокі інструменти, але оброблені концепції та продемонстровані результати є досить абстрактними. Тому рекомендується лише для другого читання. Короткий список класичних текстів на графіках можна знайти в кінці книги. Для зручності ми згадали у виносці кілька посилань, використаних у презентації. Кан, Сент-Етьєн, 26 липня 2011 р., Ален Бретто, Ален Фейсан, Франсуа Хеннекарт.
Спробуйте представити на папері структури цих переплетених сюжетів, показуючи кожного персонажа як точку, що рухається як у просторі, так і в часі. Таким чином ви отримаєте графіки (в тому значенні, що математики Кенігс і Клод Берге дають цьому терміну), цілком порівнянні з тими, що використовуються в офісах залізничних компаній, і вам буде легко це підтвердити, будучи дуже щільні, вони ніколи не передбачають суперечностей і ніколи не можуть спричинити збиття з колії або зіткнення ". François Le Lionnais (передмова до роману «Les habit noirs» Пола Феваля, зб. Букен, т. 2). Подяка Автори висловлюють щиру подяку всім, хто допомагав їм у підготовці цієї книги, і особливо Тьєррі Шарнуа (викладач Університету Кан), Франсуа Фуко (викладач Університету Сент-Етьєн), Алкіс Грекос (професор університету Брюсселя), Жорж Грекос (викладач Університету Сент-Етьєна), Жан-Марі Лебарс (викладач Університету Кан), Ерік Рейссат (професор Університету Кан), Філіп Тоффін (викладач Університет Кан).
Зміст Передмова Про авторів vii xiii 1 Основні поняття 1 1.1 Непрямі графіки. 1 1.1.1 Ступінь. 6 1.1.2 Ланцюг і цикл. 7 1.1.3 Підграфи. 9 1.2 Пов’язане розкладання. 13 1.3 Направлені графіки. 14 1.4 Прості графіки. 17 1.5 Операції на графіках. 20 1.6 Алгоритмічні зображення графіків. 20 1.7 Алгоритми та теорія складності. 22 1.7.1 Алгоритм. 22 1.7.2 Складність часу алгоритму. 24 1.7.3 Класи складності. 25 1.8 Визначення графіка з функції падіння 26 1.9 Ізоморфізми графіків. Групи автоморфізмів.27 1.10 Доповнення: деякі основні структури. 32 2 Деякі чудові графіки 35 2.1 Дводольні графіки. 35 2.2 Дерева та дерева. 39 2.2.1 Дерева. 39 2.2.2 Дерева. 45 2.3 Графіки без схеми. 48 2.4 Ейлерові та гамільтонові графіки. 50
Зміст xvii 5.2.4 Обличчя. 145 5.2.5 Формула Ейлера. 148 5.2.6 2-зв’язані площинні графіки. 154 5.3 Порівняння вкладень. 155 5.4 Теорема Куратовського. 158 5.5 Подвійний графік. 161 5.6 Перехрещення, товщина та вид графіка. 165 5.6.1 Переходи та товщина. 165 5.6.2 Вид графіка. 166 5.7 Доповнення топології та геометрії плану. 171 5.7.1 Елементи топології. 171 5.7.2 Доказ Йорданової „полігональної” теореми.175 6 Алгебраїчна теорія 183 6.1 Матриці та графіки. 183 6.1.1 Орієнтований випадок. 190 6.1.2 Ненаправлений випадок. 191 6.2 Векторні простори та графіки. 192 6.2.1 Випадок спрямованих графіків. 192 6.2.2 Випадок ненаправлених графіків. 196 6.3 Циркуляція та лінійна алгебра. 198 6.4 Площинні графіки та лінійна алгебра. 202 6.5 Доповнення лінійної алгебри. 206 6.5.1 Векторні пробіли. 206 6.5.2 Матриці. 208 6.5.3 Точкові вироби. 211 7 Розмальовка 213 7.1 Розмальовка вершин. 214 7.1.1 Загальні властивості. 214 7.1.2 Теорема Брукса. 219 7.2 Площинні графіки та карти. 222 7.3 Забарвлення країв. 227 7.4 Морфізми графіки. 232 7.4.1 Квоти графіків. 234 7.4.2 Морфізми та частки простих графіків. 236 7.4.3 Морфізми та забарвлення. 236 7,5 Досконалі графіки. 238 7.6 Список забарвлень. 242
xviii Елементи теорії графів 8 Зв'язування та розкладання на множники 245 8.1 Визначення та перші властивості. 245 8.2 Муфти у дводольних графіках. 252 8.2.1 Теорема Холла. 252 8.2.2 Мережа, пов’язана з дводольним графіком. 254 8.2.3 Алгоритмічні зауваження. 255 8.3 Муфти у довільних графіках. 256 8.4 Факторинг. 263 8.5 Деякі застосування муфт. 266 8.6 Узагальнення поняття фактора. 274 9 Автоморфізми Спектральна теорія 277 9.1 Групи перестановок. 277 9.2 Групи автоморфізмів графа та лінійного графіка 279 9.2.1 Автоморфізми, автоморфізми ребер. 279 9.2.2 Дослідження Ker α Γ. 283 9.2.3 Дослідження Im α Γ. 283 9.3 Кольоровий графік Кейлі. 287 9.4 Проблема Кеніга. 290 9.5 Групові дії. 294 9.6 Перехідні графіки. 298 9.7 Спектральна теорія графіків. 300 9.7.1 Ермітовий простір C n. 301 9.7.2 Спектр графіка. 304 9.7.3 Лапласіан графіка. 313 9.8 Хроматичний поліном. 321 10 Інші перспективи 327 10.1 Поліноми Тутта. 327 10.1.1 Основні властивості. 329 10.1.2 Поліном і хроматичний багаточлен Тутт . 336 10.1.3 Поліном Тутт і покриття дерев . 338 10.1.4 Поліном і площинність Тутти. 339 10.1.5 Інші програми. 339 10.2 Теорія Ремсі. 340 10.3 Матроїди. 347 10.4 Гіперграфи. 353
Зміст xix Бібліографія 357 Покажчик 359 Використані символи 367