Теория на графите

Графика,на която е представена връзка между отделните графи

Теорията на графите е клон от математиката, който изучава свойствата на графите.

Графиката е много удобен и естествен начин за представяне на връзките между обектите

Граф

Граф е термин от математиката, с който се означава наредена двойка 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)

Външни препратки

• Калининградская область

• Структурна оптимизация-теория

• Оригиналната статия на Ойлер