Разлика между версии на „Теория на графите“
| Ред 3: | Ред 3: | ||
'''Теорията на графите''' е '''клон от [[математика|математиката]], който изучава свойствата на графите'''. | '''Теорията на графите''' е '''клон от [[математика|математиката]], който изучава свойствата на графите'''. | ||
| − | Графиката е много удобен и естествен начин за представяне на връзките между обектите | + | ==Същност== |
| − | + | Графиката е много удобен и естествен начин за представяне на връзките между обектите. | |
| − | |||
Граф е термин от математиката, с който се означава наредена двойка G=(V,E), където: | Граф е термин от математиката, с който се означава наредена двойка G=(V,E), където: | ||
| Ред 13: | Ред 12: | ||
E е множество от двучленни подмножества на V, т.е. E ⊆ V×V. Когато в тези двучленни подмножества няма наредба, т.е. формират ненаредени двойки, е прието да се наричат ребра или още ръбове на графа, а той от своя страна — неориентиран (ненасочен) граф. Когато тези двойки са наредени, елементите на Е се наричат дъги, а графът G — ориентиран (насочен) граф. | E е множество от двучленни подмножества на V, т.е. E ⊆ V×V. Когато в тези двучленни подмножества няма наредба, т.е. формират ненаредени двойки, е прието да се наричат ребра или още ръбове на графа, а той от своя страна — неориентиран (ненасочен) граф. Когато тези двойки са наредени, елементите на Е се наричат дъги, а графът G — ориентиран (насочен) граф. | ||
| − | ==История== | + | ===История=== |
Първата работа по теория на графите е статията на Ойлер за [[Кьонигсбергските мостове]] (1736). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай - дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия.Развитието на теория на графите е много подобно на развитието на теорията на вероятностите, където голяма част от оригиналната теория е мотивирана от усилията да се разберат хазартните игри. Изследването на цикъла на polyhedra от Томас П. Киркман (1806-95) и Уилям Р. Хамилтън (1805-65) доведе до концепцията за графи. Понятието за едно дърво(свързана графика без цикли), се появява имплицитно в работата на Густав Кирхоф (1824-87),който използва графико-теоретични идеи в изчисляването на електрически мрежи или вериги.По-късно Артър Кейли (1821-95), Джеймс Дж. Силвестър (1806-97), Джордж Поля (1887-1985), както и други използват [["дървото"]], за да се изброят химически молекули. | Първата работа по теория на графите е статията на Ойлер за [[Кьонигсбергските мостове]] (1736). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай - дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия.Развитието на теория на графите е много подобно на развитието на теорията на вероятностите, където голяма част от оригиналната теория е мотивирана от усилията да се разберат хазартните игри. Изследването на цикъла на polyhedra от Томас П. Киркман (1806-95) и Уилям Р. Хамилтън (1805-65) доведе до концепцията за графи. Понятието за едно дърво(свързана графика без цикли), се появява имплицитно в работата на Густав Кирхоф (1824-87),който използва графико-теоретични идеи в изчисляването на електрически мрежи или вериги.По-късно Артър Кейли (1821-95), Джеймс Дж. Силвестър (1806-97), Джордж Поля (1887-1985), както и други използват [["дървото"]], за да се изброят химически молекули. | ||
| − | ==Приложение== | + | ===Приложение=== |
Пример за такива приложения са: | Пример за такива приложения са: | ||
Версия от 12:16, 7 април 2014
Теорията на графите е клон от математиката, който изучава свойствата на графите.
Същност
Графиката е много удобен и естествен начин за представяне на връзките между обектите.
Граф е термин от математиката, с който се означава наредена двойка 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)