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

Файл:6n-graf.svg

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

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

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

Граф

Граф е термин от математиката, с който се означава наредена двойка 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), както и други използват "дървото", за да се изброят химически молекули.

Файл:Binary tree.svg

графика-пример за двоично дърво

Приложение

Пример за такива приложения са:

химически молекули

проследяването в лабиринт

транспортна мрежа- където върховете изобразяват селищата, а свързващите ги ребра — пътищата между тях

комуникационни системи-маршрутизация на данните в интернет

двоично дърво и намира особено широко приложение като структура от данни в програмирането

родословно дърво-насочените ребра свързват родителите с децата

Вижте още

Граф (математика)

Дърво (математика)

Двоично дърво

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

Теорема на Ойлер

Източници

http://fmi.wikidot.com/tg1 http://fmi.wikidot.com/tg1

http://www.moderno.info/структурна-оптимизация-теория-на-гра.html

http://bg.wikipedia.org/wiki/Теория_на_графите http://bg.wikipedia.org/wiki/Теория_на_графите

Иржи Седлачек, „Теория на графите“, „Наука и изкуство“, София, 1967

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

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

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

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

„Статия за математическата структура дърво“