Графы. 
Рішення практичних завдань із використанням графів (З++)

Графы. Рішення практичних завдань із використанням графів (С++)

Курсовая работа Выполнил: студент 1-го курсу факультету КНиИТ, група № 121, Жучків Андрій Сергеевич Саратовский державний університет ім. Н. Г. Чернишевського.

Кафедра теоретичних основ інформатики, і інформаційних технологий Саратов 2005.

Введение

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

История виникнення теорії графов.

Родоначальником теорії графів прийнято вважати математика Леонарда Эйлера (1707−1783). Проте теорія графів багаторазово переоткрывалась різними авторами під час вирішення різних прикладних задач.

Задача про Кенигсбергских мости. На рис. 1 представлений схематичний план центральної частини міста Кенігсберг (нині Калінінград), до складу якого два береги ріки Перголя, два острови у з нею й сім що з'єднують мостів. Завдання у тому, аби пристойно оминути чотири частині суші, пройшовши в кожному мосту одного разу, і повернутися до вихідну точку. Це було вирішена (показано, що розв’язання цієї немає) Эйлером в 1736 году.

.

рис. 1.

Задача про три будинках і що трьох криницях. Є три будинки і три колодязя, якимось чином розташовані на площині. Провести від кожної дому до кожному криниці стежку те щоб стежки не перетиналися (рис. 2). Це було вирішена (показано, що ухвалено рішення немає) Куратовским в 1930 року.

.

рис. 2.

Задача про чотирьох фарбах. Розбивка на площині на непересічні області називається картою. Області на карті називаються сусідніми, якщо вони теж мають спільний кордон. Завдання полягає у розфарбуванні карти в такий спосіб, щоб навіть дві сусідні області були зафарбовані одним кольором (рис. 3). З кінця позаминулого століття відома гіпотеза, що задля цього досить чотирьох фарб. У 1976 року Апель і Хейкен опублікували вирішення завдання про чотирьох фарбах, яке базувалося на переборі варіантів з допомогою комп’ютера. Виконання цього завдання «програмним шляхом» стало прецедентом, породившим бурхливу дискусію, яка зовсім на завершено. Суть опублікованого рішення у цьому, щоб перебрати велике, але кінцеве число (близько 2000) типів потенційних контрпримеров до теоремі про чотирьох фарбах і обіцяв показати, що жодного випадок контрпримером перестав бути. Цей перебір було виконано програмою приблизно за тисячу годин роботи суперкомп’ютера. Перевірити «вручну» отримане рішення неможливо — обсяг перебору виходить далеко далеко за межі людських можливостей. Багато математики порушують питання: чи можна вважати таке «програмне доказ» дійсним доказом? Адже програмі може бути помилки… Методи формального докази правильності програм неспроможні до програм такий складності, як обговорювана. Тестування неспроможна гарантувати відсутність помилок, і в тому випадку взагалі неможливо. Отже, залишається говорити про программистскую кваліфікацію авторів, і вірити, що вони все правильно.

.

Рис. 3.

Основные поняття теорії графов Графом G (V, E) називається сукупність двох множин — непорожнього безлічі V (множества вершин) і багатьох E двухэлементных підмножин безлічі V (E — безліч ребер).

Ориентированным називається граф, у якому  — безліч упорядкованих пар вершин виду (x, y), де x називається початком, а y — кінцем дуги. Дугу (x, y) часто записують як . Подейкують, що дуга веде від вершини x на вершину y, а вершина y суміжна з вершиною x..

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

Если E є не безліччю, а набором, що містить кілька однакових елементів, то ці елементи називаються кратними ребрами, а граф називається мультиграфом.

Если елементами безлічі E не є обов’язково двухэлементные, а будь-які підмножини безлічі V, то такі елементи безлічі E називаються гипердугами, а граф називається гиперграфом.

Если задана функція F: V? M і/або F: E? M, то безліч M називається безліччю позначок, а граф називається позначеним (чи завантаженим). Як безлічі позначок зазвичай використовуються літери чи цілі числа. Якщо функція F инъективна, тобто різні вершини (ребра)имеют різні позначки, то граф називають нумерованным.

Подграфом називається граф G'(V', E'), де і/або .

Если V' = V, то G' називається остовным подграфом G.

Если , то граф G' називається власним подграфом графа G.

Подграф G'(V', E') називається правильним подграфом графа G (V, E), якщо G' містить все можливі ребра G.

Степень (валентність) вершини — на цю кількість ребер, инцидентных цією вершиною (кількість суміжних із нею вершин).

Маршрутом в графі називається чередующаяся послідовність вершин і ребер , у якій будь-які дві сусідні елемента инциденты.

Если , то маршрут замкнутий, інакше открыт.

Если все ребра різні, то маршрут називається цепью.

Если все вершини (отже, і ребра) різні, то маршрут називається простий цепью.

Замкнутая ланцюг називається циклом.

Замкнутая проста ланцюг називається простим циклом.

Граф без циклів називається ациклическим.

Для орграфов ланцюг називається шляхом, а цикл — контуром.

.

рис. 4. Маршрути, ланцюга, циклы Пример В графі, діаграма якого приведено на рис.4:

v1, v3, v1, v4 — маршрут, але з цепь;

v1, v3, v5, v2, v3, v4 — ланцюг, але з проста цепь;

v1, v4, v3, v2, v5 — проста цепь;

v1, v3, v5, v2, v3, v4, v1 — цикл, але з простий цикл;

v1, v3, v4, v1 — простий цикл.

Если граф має цикл (необов'язково простий), у якому все ребра графа за одним разу, то такий цикл називається эйлеровым циклом.

Если граф має простий цикл, у якому все вершини графа (за одним разу), такий цикл називається гамильтоновым циклом.

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

Остовом називається дерево, що містить все вершини графа.

Паросочетанием називається безліч ребер, у якому ніякі два не смежны.

Паросочетание називається максимальним, якщо ніяке його надмножество перестав бути незалежним.

Две вершини в графі пов’язані, якщо є з'єднує їх проста цепь.

Граф, у якому все вершини пов’язані, називається связным.

Граф, який складається тільки з ізольованих вершин, називається цілком несвязным.

Длиной маршруту називається кількість ребер у ньому (з повторениями).

Расстоянием між вершинами u і v називається довжина найкоротшою ланцюга , а сама знаходиться найкоротша ланцюг називається геодезической.

Диаметром графа G називається довжина длиннейшей геодезической.

Эксцентриситетом вершини v в зв’язковому графі G (V, E) називається максимальне відстань від вершини v до інших вершин графа G.

Радиусом графа G називається найменший із эксцентриситетов вершин.

Вершина v називається центральної, коли його ексцентриситет збігаються з радіусом графа.

Множество центральних вершин називається центром графа.

.

рис. 5 Эксцентриситеты вершин і центри графів (выделены).

Основные теореми теорії графов Опираясь на наведені вище визначення теорії графів, наведемо формулювання і докази теорем, які потім знайдуть свої докладання під час вирішення задач.

Теорема 1. Подвоєна сума ступенів вершин будь-якого графа дорівнює числу його ребер.

Доказательство. Нехай А1, А2, А3, …, An — вершини даного графа, a p (A1), p (А2), …, p (An) — ступеня цих вершин. Підрахуємо число ребер, збіжних у кожному вершині, і просуммируем ці числа. Це віднайденню суми ступенів всіх вершин. За такої підрахунку кожне ребро буде враховано двічі (воно завжди з'єднує дві вершины).

Отсюда слід: p (A1)+p (А2)+ … +p (An)=0,5N, чи 2(p (A1)+p (А2)+ … +p (An))=N, де N — число ребер.

Теорема 2. Кількість непарних вершин будь-якого графа четно.

Доказательство. Нехай a1, a2, a3, …, ak — це ступеня парних вершин графа, а b1, b2, b3, …, bm — ступеня непарних вершин графа. Сума a1+a2+a3+…+ak+b1+b2+b3+…+bm рівно удвічі разу перевищує ребер графа. Сума a1+a2+a3+…+ak парна (як сума парних чисел), тоді сума b1+b2+b3+…+bm мусить бути четной. Це лише у цьому разі, якщо m — парне, тобто четным є і кількість непарних вершин графа. Що було потрібно доказать.

Эта теорема має чимало цікавих следствий.

Следствие 1. Парне число знайомих у будь-якій компанії завжди четно.

Следствие 2. Кількість вершин багатогранника, у яких сходиться парне число ребер, четно.

Следствие 3. Кількість всіх людей, коли-небудь пожавших руку іншим, парне число раз, є четным.

Теорема 3. У усякому графі з n вершинами, де n більше або одно 2, завжди, знайдуться два чи більш вершини з степенями.

Доказательство. Якщо граф має n вершин, кожен із них може мати ступінь 0, 1, 2, …, (n-1). Припустимо, що у деякому графі усі його вершини мають різну ступінь, тобто, і покажемо, що цього, може неспроможна. Справді, якщо р (А)=0, це отже, що, А — ізольована вершина, і у графі не знайдеться вершини Х зі ступенем р (Х)=n-1. У насправді, ця вершина мусить бути з'єднана з (n-1) вершиною, зокрема і з А, але й, А виявилася ізольованій. Отже, в графі, що має n вершин, неможливо знайти одночасно вершини ступеня 0 і (n-1). Це означає, що з n вершин знайдуться дві, мають однакові степени.

Теорема 4. Якщо графі з n вершинами (n більше або одно 2) лише одне пара має однакову ступінь, то цьому графі завжди знайдеться або єдина ізольована вершина, або єдина вершина, сполучена з усіма другими.

Доказательство даної теореми ми опускаємо. Зупинімося лише на деякому її поясненні. Зміст цієї теореми добре роз’яснюється завданням: група, що складається з n школярів, обмінюється фотографіями. У певний час з’ясовується, що лише двоє зробили однакове число обмінів. Довести, що з школярів є або один ще який розпочинав обміну, або один вже завершив его.

Теорема 5. Якщо в графа все прості цикли четной довжини, він зовсім позбавлений жодного циклу четной довжини.

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

Теорема 6. Для здобуття права граф був эйлеровым, необхідне й досить, щоб було зв’язковим і усі його вершини мали четную степень.

Теорема 7. Для того на зв’язковому графі можна було б прокласти ланцюг АВ, що містить усі його ребра з точністю за одним разу, необхідне й досить, щоб Проте й У були єдиними непарними вершинами цього графа.

Доказательство цієї теореми дуже цікаво й притаманно теорії графів. Його слід вважати конструктивним (зверніть увагу, як використана у своїй теорема 3.6). Аби довести до вихідному графу присоединяем ребро (А, У); після цього є всі вершини графа стануть парними. Цей новий граф задовольняє всім умовам теореми 3.6, і у ньому прокласти эйлеров цикл ?. Навіть коли нині у цьому циклі видалити ребро (А, У), то залишиться бажана ланцюг АВ.

На цьому вельми цікавому прийомі грунтується доказ наступній теореми, яку варто вважати узагальненням теореми 7.

Теорема 8. Якщо даний граф є зв’язковим і має 2k вершин нечетной ступеня, у ньому можна провести k різних ланцюгів, містять усі його ребра разом рівно по одному разу.

Теорема 9. Різноманітних дерев з n перенумерованными вершинами можна побудувати nn-2.

По приводу докази цієї теореми зробимо одне зауваження. Ця теорема відома, в основному, і висновок англійського математика А. Кэли (1821—1895). Графы-деревья здавна привертали увагу учених. Сьогодні двоичные дерева використовуються не лише математиками, чи біологами, хіміками, фізиками і інженерами (докладніше звідси — в параграфі 6).

Теорема 10. Повний граф з п’ятьма вершинами перестав бути плоским.

Доказательство. Скористаємося формулою Эйлера: В-Р+Г=2, де У — число вершин плоского графа, Р — число його ребер, Р — число граней. Формула Эйлера справедлива для пласких зв’язкових графів, у яких жодного з многоугольников не лежить всередині іншого.

Эту формулу можна довести методом математичної індукції. Це доказ ми опускаємо. Зауважимо, що формула справедливою є для просторових багатогранників. Нехай усі п’ять вершин графа з'єднані друг з одним. Помічаємо, що у графі немає жодної межі, обмеженою лише двома ребрами. Якщо за ?1 позначити число таких граней, то ?2=0. Далі розмірковуємо від протилежного, а саме: припустимо, що досліджуваний граф плаский. Це означає, що з нього правильна формула Эйлера. Кількість вершин у цьому графі В=5, число ребер Р=10, тоді число граней Г=2-В+Р=2−5+10=7.

Это число можна у вигляді суми: Г=?1+?2+?3+…, де ?3 — число граней, обмежених трьома ребрами, ?4 — число граней, обмежених чотирма ребрами тощо. д.

С з іншого боку, кожне ребро є кордоном двох граней, тож число граней одно 2Р, в той час 2Р=20=3?3+4?4+…. Помноживши рівність Г=7=?3+ ?4 + ?5 + … втричі, одержимо ЗГ=21=3(?3 + ?4 + ?5 + …).

Ясно, що (3?3+3?4+3?5+…) < (3?3+4?4+ 5?5+…) чи 3Гnext;

delete temp;

return value;

}.

int peek (Node *st){ // Одержання числа без знаходження.

return st->inf;

}.

//==============================================================.

Node **graph; // Масив списків смежности.

const int vertex = 1; // Перша вершина.

FILE* fi = fopen («e_graph.txt », «r »); //Файл з матрицею смежности.

FILE* fo = fopen («e_cycle.txt », «w »); // Результуючий файл.

void add (Node*& list, int data){ //Додавання суміжною вершини.

if (!list){list=new Node;list->inf=data;list->next=0;return;}.

Node *temp=list;

while (temp->next)temp=temp->next;

Node *elem=new Node;

elem->inf=data;

elem->next=NULL;

temp->next=elem;

}.

void del (Node* &l, int key){ // Видалення вершини key зі списку.

if (l->inf==key){Node *tmp=l; l=l->next; delete tmp;}.

else{.

Node *tmp=l;

while (tmp){.

if (tmp->next) // є наступна вершина.

if (tmp->next->inf==key){ // і її бажана.

Node *tmp2=tmp->next;

tmp->next=tmp->next->next;

delete tmp2;

}.

tmp=tmp->next;

}.

}.

}.

bool eiler (Node **gr, int num){ // Визначення эйлеровости графа.

int count;

for (int i=0;inext;

}.

if (count%2==1)return 0; // ступінь непарний.

}.

return 1; // все ступеня четные.

}.

void eiler_path (Node **gr){ //Побудова циклу.

Node *P.S = init ();// Стік для пройдених вершин

int v=vertex;// 1я вершина (довільна).

int u;

push (S, v); //зберігаємо їх у стік.

while (S){ //поки стік не порожній.

v = peek (S); // поточна вершина.

if (!gr[v]){ // якщо ні инцидентных ребер

v=pop (S); fprintf (fo, «%d », v); //виводимо вершину.

}else {.

u=gr[v]->inf; push (S, u); //проходимо в таку вершину.

del (gr[v], u); del (gr[u], v); //видаляємо пройдене ребро.

}.

}.

}.

int main (){.

int n; // Кількість вершин.

int zn;// Поточне значення.

fscanf (fi, «%d » ,&n); graph=new Node*[n];

for (int i=0;i.