Алгоритм Дейкстра

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Курсовая работа. Файл: Word (.doc) в архиве zip. Язык: Украинский. Категория: Математика
Адрес этого реферата http://referat.repetitor.ua/?essayId=9493 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.
Страница 1 из 5 [Всего 5 записей]1 2 3 4 5 »

Вступ

Останнім часом дослідження в областях, що традиційно відносяться до дискретної математики, займають усе більш помітне місце. Поряд з такими класичними розділами математики, як математичний аналіз, диференціальні рівняння, у навчальних планах спеціальності "Прикладна математика" і багатьох інших спеціальностей з'явилися розділи по математичній логіці, алгебрі, комбінаториці і теорії графів. Причини цього неважко зрозуміти, просто розглянувши задачу, розв'язувану пошуку найкоротшого шляху в графі .

Елементи теорії графів

Основні визначення

Граф (graph) - пари G=(V,E), де V - безліч об'єктів довільної природи, називаних вершинами (vertices, nodes), а E - сімейство пар ei=(vi1, vi2), vij?V, називаних ребрами (edges). У загальному випадку безліч V і/чи сімейство E можуть містити нескінченне число елементів, але ми будемо розглядати тільки кінцеві графи, тобто графи, у яких як V, так і E кінцеві.

У приведеному визначенні графа E не випадково названо сімейством пар, а не безліччю. Справа в тім, що елементи E можуть бути не унікальні, тобто можливі кратні ребра. Існує інше, більш коректне визначення: граф визначається як трійка G=(V,E,?), де V - безліч вершин, E - безліч ребер, а ?=?(v,u,e) - тримісний предикат (булевська функція від трьох перемінних), що повертає True тоді і тільки тоді, коли ребро e інцидентне вершинам v і u. Однак такі "строгості" у нашому викладі є надмірними.

Якщо порядок елементів, що входять у ei, має значення, то граф називається орієнтованим (directed graph), скорочено - орграф (digraph), інакше - неорієнтованим (undirected graph). Ребра орграфа називаються дугами (arcs). Надалі будемо вважати, що термін "граф", застосовуваний без уточнень "орієнтований" чи "неорієнтований", позначає неорієнтований граф.

Приклад:

Якщо e=(v,u), те вершини v і u називаються кінцями ребра. При цьому говорять, що ребро e є суміжним (інцидентним) кожної з вершин v і u. Вершини v і u також називаються суміжними (інцидентними). У загальному випадку, допускаються ребра виду e=(v,v); такі ребра називаються петлями.

Ступінь вершини графа - це число ребер, інцидентних даній вершині, причому петлі враховуються двічі. Оскільки кожне ребро інцидентне двом вершинам, сума ступенів усіх вершин графа дорівнює подвоєній кількості ребер: Sum(deg(vi), i=1..|V|)=2?|E|.

Граф, що не містить петель і кратних ребер, називається звичайним, чи простим графом (simple graph). У багатьох публікаціях використовується інша термінологія: під графом розуміється простий граф, граф із кратними ребрами називають мультиграфом, з петлями - псевдографом.

Деякі класи графів одержали особливі найменування. Граф з будь-якою кількістю вершин, не утримуючих ребер, називається порожнім. Звичайний граф з n вершинами, будь-яка пара вершин якого з'єднана ребром, називається повним і позначається Kn (очевидно, що в повному графі n(n-1)/2 ребер).

Граф, вершини якого можна розбити на непересічні підмножини V1 і V2 так, що ніякі дві вершини, що належать тому самому підмножині, не суміжні, називається двочастковим (чи біхроматичним, чи графом Кенига) і позначається Bmn (m=|V1|, n=|V2|, m+n=|V|). Повний двочастковий граф - такий двочастковий граф, що кожна вершина безлічі V1 зв'язана з усіма вершинами безлічі V2, і навпаки; позначення - Kmn. Зауваження: повний двочастковий граф Bmn не є повним (за винятком B11=K2).

B33

Підграфом, чи частиною графа G=(V,E) називається такий граф G'=(V',E'), що V'?V і дві несуміжні вершини в G не суміжні в G'. Повним підграфом називається підграф, будь-яка пара вершин якого суміжна.

Основним підграфом (суграфом) графа G називається будь-який його підграф, що містить ту ж безліч вершин, що і G.

Ізоморфізм, гомеоморфізм

Графи G1=(V1,E1) і G2=(V2,E2) називаються ізоморфними (позначення: G1~G2), якщо між графами існує взаємо-однозначне відображення ?: G1?G2 (V1?V2, E1?E2), що зберігає відповідність між ребрами (дугами) графів, тобто для будь-якого ребра (дуги) e=(v,u) вірно: е'=?(v,u)=(?(v),?(u)) (e?E1, е'?E2). Відображення - називається ізоморфним відображенням.

Іншими словами, ізоморфні графи розрізняються тільки позначенням вершин.

Ізоморфні графи. Одне з ізоморфних відображень: (0,0), (1,3), (2,5), (3,6), (4,7), (5,2), (6,1), (7,4), (8,9), (9,8).

Характеристики графів, інваріантні відносно ізоморфизмов графів (тобто приймаючі однакові значення на ізоморфних графах), називаються інваріантами графів.

Підрозділом ребра (v1,v2) графи називається операція додавання в граф вершини v' і заміни цього ребра на два суміжних ребра (v1,v') і (v',v2): V'=V+{v'}, E'=E-{(v1,v2)}+{(v1,v')}+{(v',v2).

Граф G' називається підрозділом графа G, якщо він може бути отриманий з G шляхом кінцевого числа підрозділів ребер.

Дві графи називаються гомеоморфними, якщо для них існують ізоморфні підрозділи.

Шляхи і цикли

Шляхом у графі (чи маршрутом в орграфі) називається послідовність вершин, що чергується, і ребер (чи дуг - в орграфі) виду v0, (v0,v1), v1, ... , (vn-1,vn), vn. Число n називається довжиною шляху. Шлях без повторюваних ребер називається ланцюгом, без повторюваних вершин - простим ланцюгом. Шлях може бути замкнутим (v0=vn). Замкнутий шлях без повторюваних ребер називається циклом (чи контуром в орграфі); без повторюваних вершин (крім першої й останньої) - простим циклом.

Твердження 1. Якщо в графі існує шлях, що веде з вершини v0 у vn, то існує і простий ланцюг між цими вершинами.

Доказ: такий простий ланцюг можна побудувати, "викинувши" зі шляху всі цикли.

~

Граф називається зв'язковим, якщо існує шлях між будь-якими двома його вершинами, і незв'язним - у противному випадку. Незв'язний граф складається з декількох зв'язних компонентів (зв'язкових підграфов).

Для орграфів поняття св'язаність є більш складним: розрізняють сильну св'язаність, однобічну звязність і слабку зв'язність. Орграф називається сильно зв'язковим, якщо для будь-яких двох його вершин v і u існує як маршрут з v у u (v-u), так і з u у v (u-v). Орграф називається односторонньо зв'язковим, якщо для будь-яких двох його вершин u і v існує по крайньої один з маршрутів v-u чи u-v. Нарешті, орграф називається слабко зв'язковим, якщо зв'язний неорієнтований граф, одержуваний з цього орграфа шляхом зняття орієнтації з дуг. Очевидно, що будь-який сильно зв'язний граф є односторонньо зв'язковим, а односторонньо зв'язний - слабко зв'язковим, але не навпаки.

Дерева

Деревом називається довільний зв'язний граф без циклів.

Лема 1. Нехай G=(V,E) - зв'язний граф, вершини v1 і v2 якого не суміжні. Тоді в графі G'=(V,E+(v1,v2)) існує простий цикл, що проходить через ребро (v1,v2).

Доказ: тому що G - зв'язний, у ньому існує шлях з v2 і v1, а значить (по утвержденю 1),і простий ланцюг v2...v1. Отже, у графі G' існує шлях v2...v1(v1,v2)v2, що є простим циклом (по визначенню).

~

Лема 2. Нехай G=(V,E) - зв'язний граф, ребро e=(v1,v2) якого входить у деякий цикл. Тоді граф G'=(V,E-e) - також зв'язний, тобто при видаленні кільцевого ребра (ребра, що входить у деякий цикл) зі зв'язного графа цей граф залишається зв'язковим.

Доказ: тому що G - зв'язний, у ньому існує шлях S між будь-якими двома вершинами vi і vj. Якщо e не входить у шлях S=vi...vj, то цей шлях існує й у графі G', а виходить, G' залишається зв'язковим. Інакше (e входить у цей шлях): S=vi...v1(v1,v2)v2...vj. За умовою e - входить у деякий цикл, отже, існує замкнутий шлях C=v2(v2,v1)v1Tv2 (початком замкнутого шляху ми можемо вважати будь-яку його вершину), причому ребро e=(v1,v2) не входить у T (якщо існує шлях між вершинами, то існує і шлях, що є простим ланцюгом - див. утвердження 1). Але тоді існує шлях S'=vi...v1Tv2...vj, у котрій не входить ребро e=(v1,v2) і, отже, цей шлях існує в графі G'.

~

Лема 3. Нехай G=(V,E), p=|V|, q=|E|.

1) число зв'язних компонентів у G більше або дорівнює |V|-|E| (Nкомп.?p-q);

2) якщо в G немає циклів, то число зв'язних компонентів у G дорівнює |V|-|E| (Nкомп.=p-q).

Доказ: побудуємо порожній граф з p вершинами (очевидно, у ньому рівно p зв'язкових компонент) і будемо додавати ребра по одному.

RSSСтраница 1 из 5 [Всего 5 записей]1 2 3 4 5 »





При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
bigmir)net TOP 100 Rambler's Top100