Теорія графів та її використання у різних галузях. У фізиці: для побудови схем для розв’язання задач. У біології: для розв’язання задач з генетики. Спрощення розв’язання задач з електротехніки за допомогою графів. Математичні розваги і головоломки.
Будуємо граф, проводячи ребра(м,р), що зєднує кожну людину м з тими посадами р, які він може зайняти. На цьому графі не буде ребер, що зєднують між собою дві вершини М чи Р, тому такий граф має вигляд: додаток 1 Знову ми можемо розвязати цю задачу за допомогою дводольного графа - в цьому випадку його вершини будуть зєднані ребрами лише тоді, коли відповідні люди не є родичами. Тепер, якщо нам буде потрібно, щоб кожен учень брав участь не більше, ніж в пяти гуртках, це означатиме, що ребра від k гуртків повинні йти принаймні до k вершин із Р, і, відповідно, умова різноманітності буде виконана. Наприклад, гравець 4 грає з гравцем N - 1 в першому турі, з гравцем 2 в другому турі, з гравцем 1 в третьому турі, з гравцем 6 в четвертому турі і так далі і, нарешті, з гравцем N - 3 в (N - 1) - му турі.Вивчивши основи теорії графів, ознайомившись з розвязанням класичних задач, досліджено розвязання деяких задач за допомогою графів.
План
Зміст
Вступ 3
Задача про призначення на посаду 5
Інші формулювання 6
Спортивні змагання 8
Задача про сполучення міст 11
Знову спортивні змагання 14
Односторонній рух 16
Висновок 23
Список використаної літератури 24
Словник термінів 25
Вступ
Вывод
В моїй роботі описувались важливі методи, які можуть допомогти розвязати деякі життєві проблеми.
Вивчивши основи теорії графів, ознайомившись з розвязанням класичних задач, досліджено розвязання деяких задач за допомогою графів. Розглянуто, як можна використовувати задачі на практиці: прокладення комунікацій, розподіл посад між претендентами, складання турнірних таблиць, планування руху в містах...
Працюючи над роботою, я зрозумів, що дана тема є актуальною і перспективною в наш час.
Список литературы
Барболин М.П. Головоломки и графы. Квант, 1975, №2
В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999
Уилсон Р. Введение в теорию графов. М., Мир, 1977
Головина Л.И. Графы и их применения. Математика в школе, 1965,№ 3
Новиков Ф.А. Дискретная математика, 2001
Шедиви Я. Решение логических задач при помощи графов. - Математика в школе, 1967, № 6
Головина Л.И. і Яглом И.М., Индукция в геометрии, М., Физматгиз, 2000.
Словник термінів
Граф. Фігура, що складається з точок (вершин) і відрізків, що сполучають деякі з цих вершин. Сполучаючі відрізки можуть бути прямолінійними або криволінійними; вони називаються ребрами графа.
Дерево. Звязний граф, що не має циклів.
Многогранник. Тривимірне тіло, межа якого складається з плоских багатокутників.
Нульовий граф. Граф, що складається тільки з ізольованих вершин: граф, що не має ребер.
Ациклічний граф. Орієнтований граф, що не містить ніякого орієнтованого циклу.
Вершина графа. Або кінець якого-небудь ребра графа, або ізольована точка графа.
Гамільтонова лінія. Елементарний цикл, що проходить по всіх вершинах графа.
Грань багатокутного графа G. Частина площини, обмежена яким-небудь мінімальним циклом G або максимальним циклом C1 графа G; у останньому випадку це частина площини, що лежить поза С1; її називають також нескінченною гранню.
Степінь р(А) вершини A. Число ребер, що сходяться у вершині A. Для орієнтованого графа р(А) означає кількість ребер, що виходять, а р*(А) - кількість вхідних ребер у вершину A; в цьому випадку є два степені.
Ребро графа. Крива, що сполучає дві вершини графа і що не містить інших вершин.
Граф G*, подвійний багатокутному графові G. Багатокутний граф, кожна вершина якого відповідає певній грані графа G, а кожна грань - певній вершині графа G. Дві вершини графа G* сполучено ребром в тому і лише у тому випадку, коли відповідні грані графа G мають загальне ребро.
Дводольний граф. Граф, вершини якого можна розділити на дві непересічні множини так, що вершини однієї і тієї ж множини не сполучені між собою ребрами.
Доповнення G графа G. Граф G складається зі всіх ребер (і їх кінців), які необхідно додати до G для того, щоб вийшов повний граф.
Ізольована вершина. Вершина, з якої не виходитиме жодного ребра.
Плоский граф. Граф, якого можна накреслити на площині так, щоб його ребра перетиналися тільки в його вершинах.
Ізоморфні графи. Графи G1 і G2 ізоморфні, якщо між їх вершинами можна встановити таку взаємно однозначну відповідність, що пари вершин графа G1 в тому і лише в тому разі сполучені ребром, коли сполучені ребром відповідні пари вершин графа G2. У випадку орієнтованих графів ця відповідність повинна зберігати орієнтацію ребер.
Орієнтований граф. Граф, на якому вказані напрями всіх його ребер.
Перешийок. Інший термін, для звязуючого ребра.
Петля. Ребро графа, обидва кінці якого збігаються.
Повний граф. Граф, будь-які дві вершини якого сполучено ребром. Повний граф, у якого n вершин, має
?n(n - 1) ребер.
Правильний граф. Многокутний однорідний граф, такий, що подвійний до нього граф G* теж є однорідним.
Правильний многогранник. Многогранник, всі грані якого є рівними правильними многокутниками і в кожній вершині якого сходиться однакова кількість ребер.
Звязний граф. Граф, кожна вершина якого може бути сполучена деяким ланцюгом з будь-якою іншою його вершиною.
Звязуюче ребро. Ребро, видалення якого приводить до збільшення числа звязних компонентів графа.
Змішаний граф. Граф, на якому є як орієнтовані, так і неорієнтовані ребра.
