Основные понятия и определения.
ВУНЦ ВВС «ВВА»
филиал г. Челябинск
Реферат
на тему: «Теория графов»
Выполнил: к-т Курий А.В., 201 у/г.
Проверил: п-ль Ахкамова Ю.А.
Челябинск 2016
СОДЕРЖАНИЕ
ВВЕДЕНИЕ ............................................................................................................3
1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.................................................4
2. СПОСОБЫ ЗАДАНИЯ ГРАФОВ...................................................................16
3. ИЗОМОРФНЫЕ ГРАФЫ.................................................................................17
4. ВЗВЕШЕННЫЕ ГРАФЫ.................................................................................18
5. ПОДГРАФ.........................................................................................................18
6. ОПЕРАЦИИ НАД ГРАФАМИ........................................................................18
7. МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ.......................................................................19
8. СВЯЗНОСТЬ. КОМПОНЕНТЫ СВЯЗНОСТИ..............................................21
9. ДЕРЕВЬЯ. ЛЕС..................................................................................................21
10. ЭЙЛЕРОВЫ ГРАФЫ......................................................................................22
11. ПЛАНАРНЫЕ И ПЛОСКИЕ ГРАФЫ...........................................................24
СПИСОК ЛИТЕРАТУРЫ ....................................................................................26
ВВЕДЕНИЕ
Теория графов — «Ужас студента». Алгоритмы на графах — потрясающий ум людей их открывших.
Тема графов интересная, полезная и пугающая тема.
|
|
|
Теория графов является одним из разделов дискретной математики, который исследует свойства конечных или счетных множеств с заданными отношениями между их элементами. Особенностью этой теории является геометрический подход к изучению объектов.
Впервые понятие «граф» ввел в 1936 году венгерский математик Денеш Кëниг. Однако первая работа по теории графов была написана еще в 1736 году Леонардом Эйлером, в которой он решил «задачу о Кëнигсбергских мостах». Суть этой задачи состоит в следующем. На рис. 1 представлена схема центральной части города Кëнигсберг (ныне Калининград), которая включает два берега реки, два острова в ней и семь соединяющих их мостов. Требуется обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку.
Рис. 1
Долгие годы эта теория не находила широких приложений и была известна в основном как средство решения головоломок, логических или развлекательных задач, задач олимпиадного типа или на смекалку. При решении таких задач удобно составлять таблицы, изображать объекты точками, соединять их отрезками или стрелками, подмечать закономерности из полученных рисунков, выполнять над точками и отрезками операции, не похожие на алгебраические и геометрические.
|
|
|
И в обычной жизни очень часто мы рисуем на бумаге точки, изображающие химические вещества, населенные пункты, генеалогические деревья и соединяем эти точки линиями и стрелками, означающими некоторые отношения между рассматриваемыми объектами. Такие схемы встречаются всюду под различными названиями: электрические цепи (в физике), карты, лабиринты, диаграммы, генеалогические деревья, диаграммы организации (в экономике), социограммы (в психологии) и т.д.
В 1936 году Д. Кёниг предложил называть такие схемы графами и систематически изучать их свойства.
как отдельная математическая дисциплина теория графов была представлена лишь в 30 – е годы ХХ столетия в связи с тем, что в обиход вошли так называемые «большие системы», т.е. системы с большим числом объектов, связанных между собой разнообразными соотношениями: сети железных дорог и авиалиний, телефонные узлы на много тысяч абонентов, системы заводов – потребителей и предприятий – поставщиков, радиосхемы, большие молекулы и т.д. и т. п. Стало ясно, что разобраться в функционировании таких систем невозможно без изучения их конструкции, их структуры. Здесь и пригодилась теория графов. В середине XX века задачи теории графов стали возникать также и в чистой математике (в алгебре, топологии, теории множеств).
|
|
|
Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. Ныне она переживает эпоху бурного возрождения.
Графы используются: 1) в теории планирования и управления, 2) в теории расписаний, 3) в социологии, 4) в математической лингвистике, 5) экономике, 6) биологии, 7) химии, 8) медицине, 9) в областях прикладной математики таких, как теория автоматов, электроника, 10) в решении вероятностных и комбинаторных задач и т.д.
Наиболее близки к графам – топология и комбинаторика.
Основные понятия и определения.
Описывать графы и основные понятия удобно на рисунках.
Граф — это множество объектов.
В большинстве задач — это однотипные объекты. (Множество городов или множество домов или множество людей или множество чего-то другого однотипного)
Проще всего приводить пример на городах. Каждый из нас знает, что такое город.
Если говорить о графе как о городах, то между городами могут быть проложены дороги, а может быть где-то разрушена, не построена или же город находится на острове, моста нет, а интересуют только дороги с твердым покрытием. Несмотря на то, что дороги к такому городу нет, этот город может быть включен во множество анализируемых объектов и все объекты вместе взятые составляют совокупность объектов или проще говоря — граф.
|
|
|
Вершина графа.
Чтобы решать задачи с таким множеством, нужно каждый объект из
этого множества обозначить как что-то. Общепринято это что - то называть вершинами графа.
Наверняка вы читали учебники и видели такую запись G(V,E) или что-то похожее. Так вот — V это какой-то один объект из всего множества объектов. В нашем случае множество объектов — это города, следовательно V — это какой -то определенный город. Так как объекты не обязательно города, а слово объект может запутать, то такой объект из множества можно называть точкой, пунктом, как-то еще, но чаще всего его называют вершиной графа и обозначают буквой V. В программировании это обычно или столбец или строка двумерного массива, где массив называется или матрицей смежности или матрицей инцендентности.
E - обычно называют пару вершин. В двумерном массиве эта пара
часто номер строки + номер столбца. По номеру строки и номеру столбца проверяют соединение и если оно есть на пересечении, то это обозначают в значениях массива (матрицы) в месте пересечения строки и столбца
Дуги и Ребра графа.
В литературе, в интернете и вообще везде, где что-то написано о графах, мы будем встречать такие понятия как дуги и ребра. На этом рисунке изображены ребра графа. Т.е. это три ребра Е1, Е2 и Е3.
Дуга и ребро отличаются тем, что ребро — это такая двунаправленная связь. Захотел ушел к соседу, захотел вернулся от соседа. Если не очень понятно, то можно представить Дом, аэродром, летящий самолет и парашютиста. Парашютист может пойти из своего дома на аэродром, но когда пришел на аэродром вспомнить, что свой счастливый парашют забыл дома. Вернуться домой, взять парашют. — Такая дорога, по которой можно гулять туда и обратно называется ребром. Если парашютист находится в самолете и прыгает с самолета, но парашютист забыл в самолете надеть свой счастливый парашют, то сможет ли парашютист забрать что забыл? Такой путь, который идет только в одну сторону называется дугой. Обычно говорят что ребро соединяет две вершины, а дуга идет из одной вершины в другую
У графа могут быть два маршрута или более, которые начинаются в одной и той же вершине и заканчиваются в другой, но оба маршрута заканчиваются в одной и той же другой вершине. Такие маршруты (дуги, ребра) называются кратными.
Ориентированный граф.
На рисунке у графа одни только дуги. Дуги на графе обозначают стрелочками, потому как так ясно доступное направление. Если граф состоит из одних таких дуг, то такой граф называется ориентированным
Неориентированный граф.
На рисунке у графа одни только ребра. Ребра на графе обозначают обычными отрезками, хотя можно показать стрелочками, но сути это не изменит, потому как направление двустороннее. Такой граф называется неориентированным
Иногда можно увидеть граф, в котором дорога ведет в ту же точку, откуда выходит. Такая дорога называется петлей.
Дата добавления: 2021-03-18; просмотров: 120; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!