Матеріал з Вікіпедії - вільної енциклопедії
Теорія графів - розділ дискретної математики , Що вивчає властивості графів . У загальному сенсі граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строгому визначенні графом називається така пара множин G = (V, E) {\ displaystyle G = (V, E)} 
Теорія графів знаходить застосування, наприклад, в геоінформаційних системах (ГІС). Існуючі або знову проектовані будинки, споруди, квартали і т. П. Розглядаються як вершини, а що з'єднують їх дороги, інженерні мережі, лінії електропередач і т. п. - як ребра. Застосування різних обчислень, вироблених на такому графі, дозволяє, наприклад, знайти найкоротший об'їзний шлях або найближчий продуктовий магазин, спланувати оптимальний маршрут.
Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.
Історія виникнення теорії графів [ правити | правити код ]
Родоначальником теорії графів вважається Леонард Ейлер . У 1736 році в одному зі своїх листів він формулює і пропонує рішення завдання про семи Кенігсбергськая мостах , Що стала згодом однією з класичних задач теорії графів. Термін «граф» вперше ввів Сильвестр, Джеймс Джозеф в 1878 році в своїй статті в Nature [ Джерело не вказано 456 днів ].
Термінологія теорії графів понині не визначена строго. Зокрема, в монографії Гудман, Хідетніемі, 1981 сказано: «В програмістські світі немає єдиної думки про те, який із двох термінів" граф "Або" мережа ". Ми вибрали термін "мережа", так як він, мабуть, частіше зустрічається в прикладних областях ». Аналогічна ситуація з термінами « вершина / точка ».
Види графів:
При зображенні графів на малюнках найчастіше використовується наступна система позначень: вершини графа зображуються точками або, при конкретизації сенсу вершини, прямокутниками, овалами і ін., Де всередині фігури розкривається зміст вершини (графи блок-схем алгоритмів ). Якщо між вершинами існує ребро, то відповідні точки (фігури) з'єднуються лінією або дугою. У разі орієнтованого графа дуги замінюють стрілками, вони явно вказують спрямованість ребра. Іноді поруч з ребром розміщують пояснювальні написи, що розкривають сенс ребра, наприклад, в графах переходів кінцевих автоматів . Розрізняють планарниє і не планарні графи. планарний граф - це граф, який можна зобразити на малюнку (площині) без перетинання ребер (найпростіші - трикутник або пара пов'язаних вершин), інакше граф НЕ планарний. У тому випадку, якщо граф не містить циклів (що містять, принаймні, один шлях одноразового обходу ребер і вершин з поверненням в початкову вершину), його прийнято називати «Деревом» . Важливі види дерев в теорії графів - бінарні дерева, де кожна вершина має одне вхідне ребро і рівно два виходять, або є кінцевою - не має виходять ребер і містить одну кореневу вершину, в яку немає вхідного ребра.
Не слід плутати зображення графа власне з графом (Абстрактної структурою), оскільки одному графу можна зіставити не одне графічне представлення. Зображення покликане лише показати, які пари вершин з'єднані ребрами, а які - ні. Часто на практиці буває важко відповісти на питання, чи є два зображення моделями одного і того ж графа чи ні (іншими словами, ізоморфні Чи відповідні зображенням графи). Залежно від завдання, одні зображення можуть давати більш наочну картину, ніж інші.
До теорії графів також відноситься цілий ряд математичних проблем, не вирішених на сьогоднішній день .
- ↑ Г. С. Яблонський, В. І. Биков, А. Н. Горбань, Кінетичні моделі каталітичних реакцій , Новосибірськ: Наука (Сиб. Відділення), 1983.- 255 c.
- ↑ Євстигнєєв В.А. Застосування теорії графів в програмуванні. - М., наука , 1985. - Тираж 20000 прим. - 352 c.
- ↑ Єременко А. О. Використання теорії графів при вирішенні задач в економіці // Прогресивні технології і економіка в машинобудуванні: збірник праць VII Всеукраїнській науково-практичній конференції для студентів та учнівської молоді, м Юрга, 7-9 квітня 2016 р: в 2 т. - Томськ: Вид-во ТПУ. - 2016. - Т. 2. - С. 279-281.
- ↑ Курейчик В. М., Глушань В. М., Щербаков Л. І. Комбінаторні апаратні моделі і алгоритми в САПР. М .: Радио и связь, 1990. 216 с.
- Дістель Р. Теорія графів Пер. з англ. - Новосибірськ: Видавництво інституту математики, 2002. - 336 с. ISBN 5-86134-101-X .
- Diestel R. Graph Theory, Electronic Edition . - NY: Springer-Verlag, 2005. - С. 422.
- Басакер Р., Саати Т. Кінцеві графи і мережі. М .: Наука, 1974. 368c.
- Бєлов В. В., Воробйов Є. М., Шаталов В. Є. Теорія графів. - М.: Вища. школа, 1976. - С. 392.
- Берж К. Теорія графів та її застосування. М .: ІЛ, 1962. 320c.
- Емелічев В. А., Мельников О. І., Сарванов В. І., Тишкевич Р. І. Лекції з теорії графів. М .: Наука, 1990. 384с. (Изд.2, испр. М .: УРСС, 2009. 392 с.)
- Зиков А. А. Основи теорії графів . - М.: «Вузівська книга» , 2004. - С. 664. - ISBN 5-9502-0057-8 . (М .: Наука, 1987. 383c.)
- Хімічні додатки топології і теорії графів. Під ред. Р. Кінга. Пер. з англ. М .: Мир, 1987.
- Кірсанов М. Н. Графи в Maple. М .: Физматлит, 2007. 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
- Крістофідес Н. Теорія графів. Алгоритмічний підхід. М .: Світ, 1978. 429c.
- Кормен Т. Х. та ін. Частина VI. Алгоритми для роботи з графами // Алгоритми: побудова й аналіз = Introduction to Algorithms. - 2-е вид. - М.: Вільямс , 2006. - С. 1296. - ISBN 0-07-013151-1 .
- Оре О. теорія графів . - 2-е вид. - М.: наука , 1980. - С. 336.
- Салій В. Н. Богомолов А. М. Алгебраїчні основи теорії дискретних систем . - М.: Фізико-математична література, 1997. - ISBN 5-02-015033-9 .
- Свамі М., Тхуласіраман К. Графи, мережі та алгоритми. М: Світ, 1984. 455с.
- Татт У. Теорія графів. Пер. з англ. М .: Світ, 1988. 424 с.
- Вілсон Р. Введення в теорію графів. Пер з англ. М .: Світ, 1977. 208с.
- Харари Ф. теорія графів . - М.: світ , 1973. (Изд. 3, М .: КомКнига, 2006. - 296 с.)
- Харари Ф., Палмер Е. перерахування графів . - світ , 1977.
- Сергій Мельников. Сім і Крем під «електронним мікроскопом» // Наука і життя . - 1996. - Вип. 3. - С. 144-145. У статті йдеться про гру на графі Сим, придуманої Густавом Симмонсом.
