Разлика между версии на „Теория на графите“
Направо към навигацията
Направо към търсенето
| (Не са показани 10 междинни версии от 2 потребители) | |||
| Ред 1: | Ред 1: | ||
| − | [[image: | + | [[image: gt.png|thumb|right|Графика,на която е представена връзка между отделните графи]] |
| + | '''Теорията на графите''' е '''клон от [[математика|математиката]], който изучава свойствата на графите'''. | ||
| − | + | ==Същност== | |
| − | + | Графиката е много удобен и естествен начин за представяне на връзките между обектите. | |
| − | Графиката е много удобен и естествен начин за представяне на връзките между обектите | ||
| − | |||
| − | |||
Граф е термин от математиката, с който се означава наредена двойка G=(V,E), където: | Граф е термин от математиката, с който се означава наредена двойка G=(V,E), където: | ||
| Ред 14: | Ред 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), както и други използват [["дървото"]], за да се изброят химически молекули. | ||
| − | + | ===Приложение=== | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | =Приложение= | ||
| − | |||
| − | |||
Пример за такива приложения са: | Пример за такива приложения са: | ||
| − | химически молекули | + | *химически молекули |
| − | проследяването в лабиринт | + | *проследяването в лабиринт |
| − | транспортна мрежа- където върховете изобразяват селищата, а свързващите ги ребра — пътищата между тях | + | *транспортна мрежа - където върховете изобразяват селищата, а свързващите ги ребра — пътищата между тях |
| − | комуникационни системи-маршрутизация на данните в интернет | + | *комуникационни системи-маршрутизация на данните в интернет |
| − | двоично дърво и намира особено широко приложение като структура от данни в програмирането | + | *двоично дърво и намира особено широко приложение като структура от данни в програмирането |
| − | родословно дърво-насочените ребра свързват родителите с децата | + | *родословно дърво-насочените ребра свързват родителите с децата |
=Вижте още= | =Вижте още= | ||
| − | [[ | + | *[[Математика]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | *[[Графика]] | |
=Източници= | =Източници= | ||
| + | * Иржи Седлачек, „Теория на графите“, „Наука и изкуство“, София, 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) | ||
| + | =Външни препратки= | ||
| − | http:// | + | *[http://sovetsk39.ru/ Калининградская область] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | Калининградская область | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | *[http://www.moderno.info/%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%B0-%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F-%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F-%D0%BD%D0%B0-%D0%B3%D1%80%D0%B0.html Структурна оптимизация-теория] | ||
| + | *[http://www.kakvo.org/leonard-ojler-1707-1783-edna-unikalna-lichnost/istoria/statia Оригиналната статия на Ойлер] | ||
| − | + | [[category: Математика]][[category:Кибернетика]] | |
Текуща версия към 12:17, 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)