Теория на графите
Теорията на графите е клон от математиката, който изучава свойствата на графите.
Същност
Графиката е много удобен и естествен начин за представяне на връзките между обектите.
Граф е термин от математиката, с който се означава наредена двойка G=(V,E), където:
V е множество от елементи, наречени върхове,
E е множество от двучленни подмножества на V, т.е. E ⊆ V×V. Когато в тези двучленни подмножества няма наредба, т.е. формират ненаредени двойки, е прието да се наричат ребра или още ръбове на графа, а той от своя страна — неориентиран (ненасочен) граф. Когато тези двойки са наредени, елементите на Е се наричат дъги, а графът G — ориентиран (насочен) граф.
История
Първата работа по теория на графите е статията на Ойлер за Кьонигсбергските мостове (1736). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай - дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия.Развитието на теория на графите е много подобно на развитието на теорията на вероятностите, където голяма част от оригиналната теория е мотивирана от усилията да се разберат хазартните игри. Изследването на цикъла на polyhedra от Томас П. Киркман (1806-95) и Уилям Р. Хамилтън (1805-65) доведе до концепцията за графи. Понятието за едно дърво(свързана графика без цикли), се появява имплицитно в работата на Густав Кирхоф (1824-87),който използва графико-теоретични идеи в изчисляването на електрически мрежи или вериги.По-късно Артър Кейли (1821-95), Джеймс Дж. Силвестър (1806-97), Джордж Поля (1887-1985), както и други използват "дървото", за да се изброят химически молекули.
Приложение
Пример за такива приложения са:
- химически молекули
- проследяването в лабиринт
- транспортна мрежа - където върховете изобразяват селищата, а свързващите ги ребра — пътищата между тях
- комуникационни системи-маршрутизация на данните в интернет
- двоично дърво и намира особено широко приложение като структура от данни в програмирането
- родословно дърво-насочените ребра свързват родителите с децата
Вижте още
Източници
- Иржи Седлачек, „Теория на графите“, „Наука и изкуство“, София, 1967
- Gary Chartrand, Introductory Graph Theory
- Arun Jagota, Graph Theory, Algorithms, And Applications Summarized Simply
- Richard J. Trudeau, Introduction to Graph Theory (Dover Books on Mathematics)
- John M. Harris, Combinatorics and Graph Theory (Undergraduate Texts in Mathematics)