Федеральное государственное
образовательное бюджетное учреждение
высшего профессионального образования
«Финансовый университет
при Правительстве Российской Федерации»
(Финуниверситет)
кафедра «Математика
и статистика»
дисциплина «Элементы дискретной
математики в менеджменте»
Проверил
к.п.н., доцент
кафедры МиС
Е.Н. Трофимец
Оценка_______
«__» ________2015г.
_________________
(Подпись)
Реферат
тема: «Построение
и описание ориентированного графа согласования
для стран, участвующих в международном
конкурсе “Евровидение” с 2000 по 2015 год»
Выполнила
студентка гр. М1-1
Заболотная Влада Владимировна
«___» ______ 2015г.
_________________
(Подпись)
Санкт-Петербург, 2015
Содержание
Введение…………………………………………………………………………3
Глава 1 Основные понятия и определения
в теории графов…………………5
- История возникновения и основные
понятия………..................................5
- Маршруты, цепи, циклы и связность
графа……………………………….7
- Способы задания графов…………………………………………………...10
Глава 2 Построение и описание
собственного графа………………………...12
2.1 Построение и описание хронологической
последовательности стран, участвующий
в международном конкурсе…………………………………….12
2.2 Построение матриц смежности
и инцидентности…………………….…..14
Заключение………………………………………………………………………16
Список литературы………………………………………………………………17
Введение
Различные процессы, явления,
происходящие события можно изобразить
в виде некой системы, то есть графа. Мы
обычно даже не представляем , как часто
встречаем их в повседневной жизни, и насколько
они важны для нас. Теория графов является
очень актуальной и значимой для людей,
так как она позволяет структурировать
полученные данные, лучше и качественнее
понять исследуемый объект и выявить наиболее
благоприятный вариант из всех. Существует
множество примеров применения в разных
сферах жизни:
1)«Транспортные»
задачи, в которых вершинами графа
являются пункты, а ребрами – дороги, маршруты
(автомобильные, железные, авиационные
и др.). А также сети снабжения (энергоснабжения,
газоснабжения, снабжения товарами и т.д.),
где вершинами являются пункты производства
и потребления, а ребрами - возможные маршруты
перемещения (линии электропередач, газопроводы,
дороги и т.д.).
2)«Технологические
задачи», в которых вершины отражают
производственные элементы (заводы, цеха,
станки и т.д.), а дуги - потоки сырья, материалов
и продукции между ними.
3) «Обменные схемы»,
являющиеся моделями таких явлений как
бартер, взаимозачеты и т.д. Вершины графа
при этом описывают
участников обменной схемы (цепочки), а
дуги - потоки материальных и финансовых
ресурсов между ними.
4) «Управление проектами».
С точки зрения теории графов проект -
совокупность операций и зависимостей
между ними. Яркий пример- проект строительства
некоторого объекта. Совокупность моделей
и методов, использующих язык и результаты
теории графов ,ориентированных на решение
задач управления проектами, получила
название календарно-сетевого
планирования и управления (КСПУ).
5) «Модели коллективов
и групп, используемые в социологии,
основываются на представлении людей
или их групп в виде вершин, а отношений
между ними (например, отношений знакомства,
доверия, симпатии и т.д.) - в виде ребер
или дуг.
6) «Модели организационных
структур», в которых вершинами
являются элементы организационной системы,
а ребрами или
дугами - связи между ними(информационные,
управляющие, технологические и др.).
Цель моей работы: изучить основы
теории графов с целью дальнейшего их
применения в практической жизни.
Задачи: отразить основные понятия
и определения в теории графов, нарисовать
и описать граф из собственного примера,
построить к нему матрицы смежности и
инцидентности.
Теория графов обладает большим
количеством примеров всевозможных графов.
В частности, меня заинтересовали нестандартные
их проявления, именно поэтому в качестве
собственного примера я выбрала хронологический
порядок следования стран, участвующих
во всемирно известном конкурсе «Евровидение»
с 2000 по 2015год. Я считаю его очень актуальным
примером в преддверии наступления этого
конкурса.
Глава 1 Основные
понятия и определения в теории графов
1.1 История
возникновения и основные понятия
Теория графов в качестве дисциплины
рассматривается как раздел дискретной
математики, который исследует свойства
конечных множеств с заданными отношениями
между их элементами. Теория графов позволяет
описывать и исследовать многие технические,
экономические, биологические и социальные
системы.
Начало теории
графов датируют 1736 г., когда Л. Эйлер
решил популярную в то время
«задачу о кенигсбергских мостах».
Задача состоит в следующем: осуществить
прогулку по городу таким образом,
чтобы, пройдя ровно по одному разу каждый
мост, вернуться в то же место, откуда начиналась
прогулка. Решая эту задачу, Эйлер изобразил
Кенигсберг в виде графа, отождествив
его вершины с частями города, а ребра-
с мостами, которыми связаны эти части.
И ему удалось доказать, что искомого маршрута
не существует. Но только через 200 лет термин
«граф» впервые был введен Д. Кенигом в
1936 г.
Кенигсбергские мосты Получившийся граф
Граф – это система, которая интуитивно
может быть рассмотрена как множество
кружков и множество соединяющих их линий.
Кружки называются вершинами графа, линии
со стрелками – дугами, без стрелок –
ребрами. Ребра или дуги графа принято
обозначать буквой (е). Е – это множество
вершин графа G. Вершины обозначаются буквами
(v). V – множество вершин графа G.(см. рис.1)
Рис.1
Граф, в котором направление
линий не выделяется (все линии
являются ребрами), называется неориентированным. ( см. рис. 2)
Рис. 2
Граф, в котором направление
линий принципиально (линии являются дугами)
называется ориентированным
( см. рис. 3).
Рис. 3
Графы обычно изображаются
в виде геометрических фигур ( см. рис.
4).
Рис. 4
Петля-это дуга, начальная и конечная
вершина которой совпадают.(См.рис.5) Степень вершины- это удвоенное количество петель,
находящихся у этой вершины плюс количество
остальных прилегающих к ней ребер. (См. рис.
5)
Рис.5
Простой граф- граф без кратных ребер и петель. Пустым называется граф без
ребер. Полным называется граф, в
котором каждые две вершины смежные.
1.2 Маршруты, цепи,
циклы и связность графа.
Маршрут- последовательность вершин
и рёбер без указания их направления и
порядка следования. Цепь-
маршрут, в котором все рёбра попарно различны. Цикл- замкнутый маршрут,
являющийся цепью. Простая
цепь- маршрут, в котором все вершины
попарно различны. Простой
цикл- цикл, в котором все вершины,
кроме первой и последней, попарно различны. Связный
граф- если у графа любая пара вершин
связана.
Существует несколько видов
связных графов:
1. Граф называется гамильтоновым,
если для каждой вершины графа найдется
маршрут, начинающийся и заканчивающийся
в этой вершине, и проходящий через все
вершины только один раз. Такой маршрут
называется гамильтоновым циклом. Гамильтоновы
графы применяются для моделирования
многих практических задач, например,
при составлении расписания движения
поездов. Основой для их решения служит
классическая задача коммивояжера: коммивояжер должен
совершить поездку по городам и вернуться
обратно, побывав в каждом городе ровно
один раз, сведя при этом затраты на передвижения
к минимуму. Вершины графа это города,
а ребра — связывающие их
дороги. Кроме того, каждое ребро оснащено
весом, обозначающим транспортные затраты,
необходимые для путешествия по
соответствующей дороге (расстояние между
городами или время движения по дороге).
Необходимо найти гамильтонов цикл минимального
общего веса. (См. рис. 6)
Рис.6
2. Граф называется эйлеровым,
если для всякой вершины графа найдется
маршрут начинающейся и заканчивающейся
в этой вершине и проходящий через каждое
ребро только один раз. Такой маршрут называется
эйлеровым циклом. (См. рис. 7)
Рис.7
3. Граф называется деревом,
если он связан и не имеет циклов.
Свойства деревьев:
1.Любая пара вершин соединена единственным
маршрутом.
2.Количество ребер меньше на одну
чем вершин.
3.Удаление хотя бы одного ребра не
нарушает его структуру.
4.Если в дерево добавить хотя бы одно
ребро то появиться цикл.
Дерево называется деревом
с корнем, если одна вершина
выделена и расположена выше остальных. Вершины, расположенные
под одной вершиной, называется ее сыновьями,
а сама вершина отцом. Вершины, не
имеющие сыновей, называются листьями. Вершины отличные
от корня и листьев называют внутренними.
Дерево, корнем которого является одна
из вершин данного дерева, называется поддеревом.
Деревья используются
для описания структур организаций, предприятий
и др. Такие структуры называются иерархическими.
Примером может служить структура управления,
где корень дерева- управляющий, с ним
связаны непосредственно подчиненные
ему руководители - вершины 2-го уровня,
которым, в свою очередь непосредственно
подчинены другие- вершины 2-го уровня
и так вплоть до исполнителей нижнего
уровня- листьев. Дерево образует структуру
предприятия, где корень- само предприятие,
под ним- входящие в него цехи и службы,
ниже- входящие в цехи участки и т.д. (См.
рис. 8)
Рис.8
Также существует несколько
видов плоских графов:
Плоский граф — это граф, нарисованный таким
образом, что его ребра не пересекаются.
Говорят, что граф допускает плоскую
укладку, если его можно нарисовать
как плоский. Также плоские графы называют планарными. (См. рис. 9)
Рис. 9
В планарном графе можно говорить не
только о вершинах и ребрах, но и о гранях.
Грань —
это часть плоскости, окруженная простым
циклом и не содержащая внутри себя других
элементов графа.
Внешняя грань —
это вся плоскость, окружающая плоский
граф.
Существуют и непланарные графы. На рис. 10 показаны два таких
графа: полный пятивершинник и полный
двудольный граф. Для них есть специальные
обозначения: K5 и K3,3 соответственно.
Рис.10
Двудольный
граф — это граф, вершины которого разбиты
на две доли (части), а ребра проходят только
между вершинами из разных частей.
1.3 Способы задания
графов
Существует несколько способов
задания графов. Мы рассматривали графический
(геометрический) способ. Не следует путать
изображение графа с собственно графом
(абстрактной структурой), поскольку одному
графу можно сопоставить не одно графическое
представление. Изображение призвано
лишь показать, какие пары вершин соединены
рёбрами, а какие — нет. Часто на практике
бывает трудно ответить на вопрос, являются
ли два изображения моделями одного и
того же графа или нет (другими словами,
изоморфны ли соответствующие изображениям
графы). В зависимости от задачи, одни изображения
могут давать более наглядную картину,
чем другие. Очевидно, что графический
способ представления графов непригоден
для ПК. Поэтому существуют другие способы
представления графов. Поэтому существует
способ задания графов с помощью матриц
инцидентности и смежности.
Матрица
инцидентности. Это матрица А с n строками,
соответствующими вершинам, и m столбцами,
соответствующего рёбрам. Для ориентированного
графа столбец, соответствующий дуге (х,y)содержит
- 1 в
строке, соответствующей вершине х и 1,
в строке, соответствующей вершине у.
Во всех остальных 0.
Петлю, т.е. дугу (х,х) можно
представлять иным значением в строке х,
например, 2.
Если граф неориентированный, то столбец,
соответствуюший ребру (х,у) содержит 1,
соответствующие х и у и
нули во всех остальных строках. Например
матрица инцидентности для данного графа.
(См. рис. 11)
Рис.11
Матрица смежности. Это матрица n×n где n -
число вершин, где bij =
1, если существует ребро, идущее из
вершины х в вершину у и bij =
0 в противном случае. Например матрица
смежности для данного графа. (См. рис.
12)
Рис. 12
Глава 2 Построение
и описание собственного графа
- Построение
и описание хронологической последовательности
стран, участвующий в международном конкурсе
Евровидение – это ежегодный
музыкальный конкурс песен, который проводится
в основном среди исполнителей из стран,
входящих в Европейский Вещательный Союз
(ЕВС). От каждой страны-участницы на «Евровидение»
отправляется один участник, который исполняет
одну песню. Победитель конкурса определяется
путём голосования телезрителей и жюри
из каждой участвующей страны. Основатель
этого конкурса ,Марсель Бесон, который
очень любил этот проект, видел в нем возможность
объединения наций в послевоенное время.
Это событие превратилось в традицию
, которая ежегодно объединяет людей в
единое целое, при этом сохраняя культурные
различия каждого. Что может больше сблизить
людей , как ни песня? Особенно сейчас,
в неспокойное для многих время. «Евровидение»
сегодня – это одно из наиболее ожидаемых
и популярных событий в музыкальной жизни
Европы. Ежегодно за этим конкурсом наблюдает
более 100 миллионов телезрителей по всему
миру. Мы хорошо помним победителей и их
песни, которые впоследствии становятся
хитами, но забываем места в которых побывал
этот удивительный конкурс. Это легендарное
событие насчитывает за собой уже почти
60 лет. В данной работе я рассмотрю страны
за последние 15 лет. ( см. рис.13)
Рис.13
Вершинами данного графа будут
являться сами страны ,которые участвовали
в конкурсе за определенный период времени:
Швеция, Дания, Эстония, Латвия, Турция,
Украина, Греция, Финляндия, Сербия, Россия,
Норвегия ,Германия, Азербайджан, Австрия.
Между этими странами существует
взаимодействие, в виде хронологической
цепочки перемещения конкурса из одной
страны в другую с 2000 по 2015 год. Данный
граф будет являться ориентированным,
так как нам принципиально знать перемещение,
то есть вершины графа будут соединены
дугами. Рассмотрим , как будут смотреться
эти связи графически.(см. рис.14)