Построение и описание ориентированного графа согласования для стран, участвующих в международном конкурсе “Евровидение” с 2000 по 2015 год
Творческая работа, 31 Мая 2015, автор: пользователь скрыл имя
Описание работы
Цель моей работы: изучить основы теории графов с целью дальнейшего их применения в практической жизни.
Задачи: отразить основные понятия и определения в теории графов, нарисовать и описать граф из собственного примера, построить к нему матрицы смежности и инцидентности.
Содержание работы
Введение…………………………………………………………………………3
Глава 1 Основные понятия и определения в теории графов…………………5
История возникновения и основные понятия………..................................5
Маршруты, цепи, циклы и связность графа……………………………….7
Способы задания графов…………………………………………………...10
Глава 2 Построение и описание собственного графа………………………...12
2.1 Построение и описание хронологической последовательности стран, участвующий в международном конкурсе…………………………………….12
2.2 Построение матриц смежности и инцидентности…………………….…..14
Заключение………………………………………………………………………16
Список литературы…………………
Файлы: 1 файл
Реферативное сообщение.docx
— 413.39 Кб (Скачать файл)Рис.14
Мы можем видеть, что все дуги довольно тесно расположены друг к другу, также как и страны, принимающие на своей территории данное мероприятие. По правилам данного конкурса право привезти «Евровидение» к себе в страну предоставляется победителю. На этом графе мы видим у некоторых вершин 3и 4 степени ( если рассматривать историю этого конкурса полностью, то можно выявить своеобразных лидеров), а это, в свою очередь, позволяет нам сделать некий приблизительный прогноз на призовые места и дальнейшее место проведения конкурса, хотя победителем может стать кто угодно.
- Построение матриц смежности и инцидентности
Матрица смежности будет выглядеть следующим образом. Где A, B,C,...N-вершины графа. Значение 1- если для двух соседних вершин есть соединяющая дуга и 0- если нет соединяющей дуги. (См. рис. 15)
Рис.15
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N | |
A |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
B |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
C |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
D |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
E |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
F |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
G |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
H |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
I |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
J |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
K |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
L |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
M |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
N |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
А-матрица смежности графа
Матрица инцидентности: A,B,C...N-вершины; е1,е2...е15- дуги; 1- если дуга входит в вершину, 0- если нет дуги; -1 –если дуга выходит из вершины. (См.рис.16) Рис.16
e1 |
e2 |
e3 |
e4 |
e5 |
e6 |
e7 |
e8 |
e9 |
e10 |
e11 |
e12 |
e13 |
e14 |
e15 | |
A |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
B |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
C |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
D |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
E |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
F |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
G |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
H |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
I |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
J |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
K |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
0 |
L |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
0 |
M |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
0 |
0 |
N |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
В- матрица инцидентности графа
Заключение
В своей работе я отразила основные понятия и определения теории графов. Вследствие анализа данной теории, я увидела, что графы применяются практически во всех областях жизнедеятельности человека, их можно встретить где угодно и в каких угодно проявлениях. Также узнала ,что существует множество всевозможных видов графов, обладающих определенными свойствами. Меня заинтересовало нестандартное их применение, поэтому в своей работе я построила и описала граф для стран, участвующих в международном конкурсе «Евровидение» с 2000 по 2015 год. На основе полученного графа мы увидели хронологию путешествий этого конкурса и его примерную геолокацию. Благодаря различным степеням вершин можно выявить многократных победителей и своеобразных фаворитов. Использование теории графов в повседневной жизни значительно упрощает поиск нужной информации и дает наиболее продуктивное для нас решение.
Список использованной литературы:
1. Кундышева, Е.С. Математика: учебник для экономистов/ Е.С. Кундышева. – 4-е изд. - М.: Дашков и К°, 2013. - 564 с.
2. Балдин, К.В. Математические методы и модели в экономике: учебник/ К.В. Балдин, В.Н. Башлыков, А.В. Рукосуев; под общ. ред. К.В. Балдина. – М.: ФЛИНТА: НОУ ВПО МПСИ,2012. – 328 с.
3. Д. В. Карпов. Теория графов. Интернет публикация, 2012. – 340с;
4. Кузнецов Б.Т. Математика: учебник/ Б.Т. Кузнецов. - М.: ЮНИТИ-ДАНА, 2010.
5. https://en.wikipedia.org/wiki/Graph_theory.
6. http://dmtsoft.ru/bn/391/as/oneaticleshablon/