6229

Теорія графів. Розвязок задачі на основі графів на мові C++

Курсовая

Информатика, кибернетика и программирование

Теорія графів - це галузь дискретної математики, особливістю якої є геометричний підхід до вивчення об'єктів. Вона перебуває зараз у самому розквіті. Розділ теорії графів Зв'язність графів, що розглядається у цій роботі, є дуже актуальною на сьогоднішній день. Наприклад її прямим застосуванням є теорія сітей – та її додаток - теорія електронних сітей...

Украинкский

2013-01-03

583.5 KB

48 чел.

Вступ

Теорія графів - це галузь дискретної математики, особливістю якої є геометричний підхід до вивчення об'єктів. Вона перебуває зараз у самому розквіті. Розділ теорії графів «Зв’язність графів», що розглядається у цій роботі, є дуже актуальною на сьогоднішній день. Наприклад її прямим застосуванням є теорія сітей – та її додаток - теорія електронних сітей, що активно використовуються у комп’ютерних мережах сьогодення.

У цій роботі розглядається розв’язок задачі, основою якої є граф. Робота поділена на чотири частини, що у свою чергу включають в себе підпункти, висновок, список використаної літератури та додаток (текст програми на мові C++).

У першому розділі ми розглядаємо текст задачі й аналізуємо його саме щодо теорії графів.

У другому пункті, що поділений на дві частини розглядається докладно метод вирішення задачі й алгоритм написання програми на мові C++. 

Третя частина розділена на три підпункти: інструкція користувача, розрахунок контрольних прикладів й аналіз результатів. Розрахунок контрольних прикладів означає рішення прикладів, подібних нашій задачі без використання програми й за допомогою неї. В той час як аналіз результатів полягає у тому, що ми повинні визначити залежність швидкості програми від розміру графу.

Останній, четвертий, розділ включає  в себе приклади практичного застосування даної програми.

Тобто ця курсова робота є повним розв’язком задачі, що і є метою створення даної праці.

  1.  ПОСТАНОВКА ЗАДАЧІ

На олімпіаду прибуло N людей. Деякі з них знайомі між собою. Чи можливо опосередковано перезнайомити їх усіх між собою? (Незнайомі люди можуть познайомитися лише через спільного знайомого).

Постановка задачі у термінах теорії графів.

Сформулюємо умову задачі в термінах теорії графів. Нехай кожному учаснику відповідає вершина графа. Тоді той факт, що два учасника знайомі між собою зобразимо у вигляді ребра, що зєднує відповідні їм вершини. Можливість опосередковано познайомити двох учасників означає, що у графі існує шлях між відповідними вершинами. Можливість познайомити усіх учасників означає  існування шляху між будь-якими двома вершинами графа. Такі графи називаються зв’язними. Тобто ми повинні перевірити граф на звязність.

  1.  МЕТОД ВИРІШЕННЯ
    1.  Метод вирішення

Нехай N людей, що прибули на олімпіаду – це N вершин графа. Ребра цього графа вказують на зв'язки між людьми – тобто знайомі вони чи ні; при чому ребра ці – неорієнтовані, тому що, якщо людина під номером 1 знає людину під номером 2, то очевидно, що і людина з номером 2 знає людину з номером 1.

З цього можна зробити висновок, що для вирішення задачі достатньо встановити, чи є зв'язним граф, який визначається матрицею суміжності, елементи якої  а[i,j] дорівнюють 1, якщо люди з номерами i і  j  знайомі і дорівнюють 0 в іншому випадку. Як зазаначалося вище, граф називається зв'язним, якщо існує шлях між будь-якими парами його вершин. Зрозуміло, що шлях між вершинами i і  j  в такому графі визначає можливу послідовність знайомств, що дозволяють познайомити  людей з номерами i і  j .

Для визначення звязності графа можно скористатися методом пошуку в ширину. Його ідея полягає в тому, щоб відвідувати вершини в порядку їх віддаленості від деякої заздалегідь обраної або зазначеної стартової вершини α. Інакше кажучи, спочатку відвідується сама вершина α, потім усі вершини, суміжні з нею, тобто, що перебувають від неї на відстані 1, потім вершини, що перебувають від неї на відстані 2, і т.д. (Рис.1).

 

Рис.1 – Зв’язний граф

Розглянемо алгоритм пошуку завширшки із заданою стартовою вершиною α. Спочатку всі вершини позначаються як нові. Першою відвідується вершина α, вона стає єдиною відкритою вершиною. Надалі кожний черговий крок починається з вибору деякої відкритої вершини χ. Ця вершина стає активною. Далі досліджуються ребра, інцидентні активній вершині. Якщо таке ребро χ з'єднує вершину з новою вершиною γ, то вершина γ відвідується й перетворюється у відкриту. Коли всі ребра, інцидентні активній вершині, досліджені, вона перестає бути активною й стає закритою. Після цього вибирається нова активна вершина, і описані дії повторюються. Процес закінчується, коли безліч відкритих вершин стає порожнім.

Якщо розглядати докладніше метод по відношенню саме для нашої задачі.ю то він виглядатиме так.

На початковому етапі в чергу поміщається деяка початкова вершина, наприклад вершина під номером 1.

На кожній з наступних ітерацій (поки черга не порожня) виконуються наступні дії:

    -вибирається вершина із черги;

    -визначаються вершини, їй суміжні і які в черзі ще не були, і містяться в чергу.

Якщо в результаті таких дій усі вершини побували в черзі (а для цього зручніше підраховувати кількість вершин, що там побували), то граф зв'язний, інакше не зв'язний. Для маркування вершин, що побували в черзі, можна використовувати масив розміру N з елементами 0 і 1.

  1.  Алгоритм вирішення задачі
  2.  Запускається функція розрахунку часу.
  3.  Вводяться данні (Табл.1)

Таблиця 1

Таблиця змінних

Данні

Тип данних

Описання

n

int const

Максимальна кількість людей, що можуть прийти на олімпіаду

N

int

Кількість людей, що прибули на олімпіаду

G[n][n]

int

Квадратна матриця суміжності G

i, j, k

int

Змінні для циклів

V[n]

int

Вектор досягнень

kol

int

Кількість елементів в у векторі досягнень V[n]

marker

int

Помітка, що приймає значення 1 або 0 в залежності від того була вершина в V[n] чи ні

  1.  Відкривається файл fs1.txt й опустошається.
  2.  Файл fs1.txt перевіряється на помилки: можливо файл відсутній або просто закритий для читання інформації. Якщо файл не пройшов перевірку на помилки – виводиться «Error open file.» й програма завершується. Якщо не виявляються помилки - програма переходить до наступного кроку.
  3.  Якщо файл fs2.txt – існує, то він перезапускається й опустошається, якщо ж – ні, то створюється автоматично програмою.
  4.   Файл fs2.txt перевіряється на помилки: можливо файл просто закритий для запису інформації. Якщо файл не пройшов перевірку на помилки – виводиться «Error open file.» й програма завершується. Якщо не виявляються помилки - програма переходить до наступного кроку.
  5.  Зчитується інформація з файлу fs1.txt, що відкритий для читання: N – кількість прибувших на олімпіаду, а також кожен елемент матриці суміжності G[i][j].
  6.  Файл, що був відкритий для читання закривається, так як потрібно інформація з нього дісталася і він нам більше не потрібен.
  7.  Кожен елемент вектора V[j] досягнень приймається за 0, а перший елемент вектора – за першу вершину. Кількість елементів у векторі досягнень приймає значення «1».
  8.  Продивляємось елементи в рядку з номером 1 і знаходимо одиниці - тобто вершини, суміжні з першою вершиною (люди знайомі з людиною під номером один), при знаходженні пар ставиться позначка marker=0.
  9.  Передивляємося елементи вектора досягнень, якщо людина за певним номером там присутня, то ставиться marker=1.
  10.  Якщо позначка marker=0, тобто людина ще не присутня у векторі досягнень, то заносимо її туди, а кількіть «kol» елементів в векторі збільшується на 1.
  11.   Після перегляду всіх вершин, дивимося на кількість елементів у векторі досягнень, якщо вона буде дорівнювати заданій цифрі N – кількості прибувших на олімпіаду, то у файл fs2.txt заноситься інформація у вигляді слова “Yes”. Якщо ж кількість не дорівнює заданому числу, то видається інформація “Nо”.
  12.  Час початку й кінця роботи програми виводиться у цей же файл fs2.txt.
  13.  Закривається файл fs2.txt.
  14.  Кінець програми.

  1.  ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ВИРІШЕННЯ ЗАДАЧІ
    1.  Інструкція користувача

Для реалізації  цієї задачі була створена програма мовою С++. Вона є досить легка у використанні. З початку необхідно знайти файл з назвою – fs1і розширенням – txt (fs1.txt) (Рис.1).

Рис.1

В цьому файлі повинна зберігатися початкова інформація. У першій строчці вводиться кількість людей, що прийшли на олімпіаду, іншими словами – кількість вершин графа (Рис.2).


Рис.2

У наступному кроці вводиться матриця суміжності у такому вигляді (Рис.3).

Рис.3

Далі буде безпосередній запуск програми. Закриваєте файл fs1.txt – він Вам більше не потрібен. У цій же течці шукаєте файл GRAF.exe (Рис.4).

Рис.4

Запускаєте файл GRAF.exe, він відкривається і одразу ж закривається, уся інформація про результати вирішення поміщається у файл FS2.TXT, що створюється автоматично із закінченням роботи GRAF.exe (Рис.5).

 

Рис.5

У файлі знаходиться відповідь на основне запитання задачі: «Чи можливо опосередковано перезнайомити їх усіх між собою?» - Yes або No, а також час початку й кінця роботи програми, відповідно (Рис.6).  

Рис.6

Відповідно, якщо у файлі знаходиться слово Yes – людей можливо перезнайомити, тобто граф – звязний, якщо ж Noне можливо, тобто граф – не зв’язний.

  1.  Розрахунок контрольних прикладів

№ 1. Вирішення задачі вручну. Початкові данні: N=5

Графічне зображення графа, що відображає хто із ким знайомий (Рис.7).

                          V2

Рис.7

Матриця суміжності по графу:

X

1

2

3

4

5

1

0

1

0

1

1

2

1

0

1

1

0

3

1

1

0

0

1

4

0

1

0

0

1

5

1

0

1

1

0

Виконуємо такі дії:

  1.  Помічаємо вершину №1.

X

1

2

3

4

5

1

0

1

0

1

1

2

1

0

1

1

0

3

0

1

0

0

1

4

1

1

0

0

1

5

1

0

1

1

0

  1.  Шукаємо вершини суміжні вершині №1 – це вершини№2, №4, №5. Помічаємо їх також.

X

1

2

3

4

5

1

0

1

0

1

1

2

1

0

1

1

0

3

0

1

0

0

1

4

1

1

0

0

1

5

1

0

1

1

0

  1.  Серед непомічених вершин шукаємо вершини суміжні вершинам №2 і №5 – це №3. Помічаємо знайдену вершину.

X

1

2

3

4

5

1

0

1

0

1

1

2

1

0

1

1

0

3

0

1

0

0

1

4

1

1

0

0

1

5

1

0

1

1

0

  1.  Кількість помічених вершин дорівнює кількості вершин графа взагалі, отже граф зв'язний – всіх людей можливо перезнайомити між собою!

№2. Вирішення задачі за допомогою написаної програми.

Початкові данні містяться в файлі “fs1.txt”: N=6, матриця суміжності (Рис.8).  

Рис.8

Запускаємо файл GRAF.exe й отримуємо відповідь у файлі FS2.TXT (Рис.9).

Рис.9

№3. Вирішення задачі за допомогою написаної програми.

Початкові данні містяться в файлі “fs1.txt”: N=6, матриця суміжності (Рис.10).  

X

1

2

3

4

5

6

1

0

1

0

0

1

0

2

1

0

1

1

0

0

3

0

1

0

0

1

0

4

1

1

0

0

1

0

5

1

0

1

1

0

1

6

0

0

0

1

0

0

Рис.10

Запускаємо файл GRAF.exe й отримуємо відповідь у файлі FS2.TXT (Рис.11).

Рис.11

№4. Вирішення задачі за допомогою написаної програми.

Початкові данні містяться в файлі “fs1.txt”: N=7, матриця суміжності (Рис.12).  

X

1

2

3

4

5

6

7

1

0

1

0

0

1

0

0

2

1

0

0

0

0

0

0

3

0

0

0

0

0

0

0

4

1

0

0

0

1

0

1

5

1

0

0

1

0

1

1

6

0

0

0

0

0

0

0

7

0

0

0

1

1

0

0

Рис.12

Запускаємо файл GRAF.exe й отримуємо відповідь у файлі FS2.TXT (Рис.13).

Рис.13

  1.  Аналіз результатів

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

  1.  ПРАКТИЧНЕ ЗАСТОСУВАННЯ

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

  1.  У відстежуванні розповсюдження вірусу в комп'ютерних мережах;
  2.  У визначенні можливості розповсюдження інформації від єдиного джерела;
  3.  У хвильовому алгоритмі в трассуванні друкованих плат;
  4.  В алгоритмі Форда-Фулкерсона;
  5.  У теорії сітей та теорії електронних сітей й тд.

ВИСНОВОК

У процесі проведеної роботи ми:

  1.  Вирішили основне запитання задачі;
  2.  Вивчили один з методів доказу звязності графу: пошук у ширину;
  3.  Навчились використовувати метод пошуку у ширину на практиці;
  4.  Створили зручну у користуванні програму вирішення даної задачі;
  5.  Дізнались про практичне застосування отриманої програми окрім заданої задачі;

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

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

  1.  Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978
  2.  Харари Т. Теория графов.- М.,1973
  3.  Братко И. Алгоритмы искусственного интеллекта на языке Prolog, 3-е издание  
  4.  Москинова Г. Дискретная математика. Математика для менеджера в примерах и упражнениях.- М., 2000
  5.  Новиков Ф. Дискретная математика для программистов.- С.-П., 2000
  6.  Ловас Л. Прикладные задачи теории графов. Теорія паросочетаний в математике, физике, химии.-  USA, 1896
  7.  Ананий В. Левитин Алгоритмы: введение в разработку и аналіз - М., 2006.

ДОДАТОК

#include <iostream.h>

#include <fstream.h>

#include <stdio.h>

#include <dos.h>

int main(void)

{

         struct dostime_t t;

 _dos_gettime(&t);  // оператори розрахунку часу

int const n=100; // максимальна кількість людей

int G[n][n];  // G- матриця суміжності

int i,j,k;  // змінні для циклів

int N;  // N – поточна кількість людей

        int V[n];  // вектор досяжності

        int kol=0,marker=0; // кількість досяжних людей для першої людини з урахуванням першої людини; помітка, приймає значення 1 чи 0, указує чи побувала вершина (людина) у векторі досяжності

   FILE *f1,*f2;  // файли для введення та запису даних

if ((f1 = fopen("fs1.txt","rt"))==0)  // відкриття файлу в режимі читання й подальша перевірка на помилку відкриття

{

 cout << "Error open file.";

 return 0;

}

if ((f2 = fopen("fs2.txt","wt"))==0)  // відкриття файлу або його створення та подальша перевірка на помилку відкриття

{

 cout << "Error open file.";

 return 0;

}

fscanf(f1,"%d",&N);  // зчитує з файлу f1 ціле число й заносить у значення перемінної N

for (i=0; i<N; i++)  // перебирає строки масиву

{

 for (j=0; j<N; j++) // перебирає елементи строк масиву

 {

  fscanf(f1,"%d",&G[i][j]);  // зчитує з файлу f2 матрицю суміжності G

 }

}

fclose(f1);  // після зчитування потрібної нам інформації, закриваємо файл f1

for(j=0;j<N;j++)

         V[j]=0; // обнулююємо вектор досяжності

 V[0]=1; // перший елемент вектора позначаємо як першу вершину графа

kol=1; // збільшує кількість людей, що потрапили до вектора досяжності

for (i=0;i<kol;i++)

{

 for(j=0;j<N;j++)

 {

  if (G[i][j]==1)  // якщо i-та людина знайома з j-тою

  {

   marker=0;

   for(k=0;k<kol;k++)

  {

  if(V[k]==(j+1))   // перевірка на  присутність людини у векторі досяжності

  {

   marker=1; // вказує на присутність людини у векторі

     break;

    }

   }

   if (marker==0) // якщо людина не присутня у векторі досяжності    {

    V[kol]=j+1;  // то додаємо людину у вектор досяжності

    kol++;  // збільшуємо кількість людей, що потрапили до вектора досяжності

   }

  }

 }

}  // після перевірки усіх вершин графу (людей) підрахуємо їх кількість у векторі досяжності

if (kol==N)  // якщо кількість людей у векторі досяжності дорівнює поточній кількості людей, то граф – зв’язний, тобто всіх людей можливо перезнайомити

       {

fprintf(f2,"%s","Yes");  // у файл f2 заноситься слово "Yes"

}

else

{

fprintf(f2,"%s","No"); // інакше запишемо відповідь No до файлу f2

}

        fprintf(f2,"\n @$The time of start is: %2d:%02d:%02d.%02d\n", t.hour, t.minute, t.second, t.hsecond);  // у файл f2 вводиться час початку роботи програми

_dos_gettime(&t);

fprintf(f2,"\n @$The time of end is: %2d:%02d:%02d.%02d\n", t.hour, t.minute, t.second, t.hsecond);  // у файл f2 вводиться час кінця роботи програми

fclose(f2); // закриваємо файл з результатами вирішення

 return 0;

}  // програма завершується


v2

v1        V1

5      V5

v4   V4

v3   V3


 

А также другие работы, которые могут Вас заинтересовать

81043. Внешняя политика РФ в начале 21-го века 39.4 KB
  Изменение ситуации в мире приводит к возникновению нескольких исторических вызовов России что диктует необходимость скорректировать ее политику. Там где позволяют условия в Белоруссии и возможно в Армении России следует содействовать относительно безболезненной смене правящих режимов предоставляя при этом соответствующие гарантии. Что делать Требовать включения в НАТО самой России Это наверное малореалистично к тому же может препятствовать необходимому усилению азиатского вектора отечественной политики. Несмотря на все имеющиеся...
81044. Образование СНГ. Становление отношений РФ со странами СНГ 43.13 KB
  Становление отношений РФ со странами СНГ Содру́жество Незави́симых Госуда́рств СНГ региональная международная организация международный договор призванная регулировать отношения сотрудничества между странами ранее входившими в состав СССР. СНГ не является надгосударственным образованием и функционирует на добровольной основе. СНГ было основано главами БССР РСФСР и Украины путём подписания 8 декабря 1991 года в Вискулях Беловежская пуща под Брестом Беларусь Соглашения о создании Содружества Независимых Государств известно в СМИ...
81045. Интеграционные процессы в странах СНГ 44.53 KB
  После получения независимости страны СНГ при наличии разности видения перспектив и возможностей строят рыночную экономику и демократические государства. Национальная идея как основа государственности получила закрепление в преамбуле многих конституций стран СНГ. В процессе жизнедеятельности страны СНГ прошли сложный путь само индетификации определения целей прерогатив развития.
81046. Этапы эволюции ЕС. Правовая основа ЕС 48.21 KB
  Хартию основных социальных прав трудящихся призванную сделать более гармоничными индивидуальные и коллективные права трудящихся и закрепить уже завоеванные права. Европейское право является самостоятельной правовой системой находящейся на стыке национального права государств-членов ЕС и права международного. К функциональным принципам относятся принцип верховенства права и принцип прямого действия. Принцип верховенства права ЕС означает приоритет норм права ЕС над нормами национального...
81047. Взаимоотношения ЕС и России. Зоны противоречий ЕС-РФ 49.13 KB
  В практическом плане это должно было вылиться в сближение экономик России и Евросоюза углубление совместного сотрудничества в борьбе с организованной преступностью терроризмом незаконной миграцией а в перспективе и в отмену визового режима. По статистике на Евросоюз приходится половина объёма внешней торговли России а государстваучастники этой организации являются крупнейшими прямыми инвесторами в российскую экономику. ЕС главный для России источник современных технологий.
81048. Азиатско-тихоокеанский регион в международной системе 52.02 KB
  Развитие права норм и механизмов регулирования международных отношений в АТР как и в других регионах мира связано с такими организациями как: Ассоциация государств ЮгоВосточной Азии АСЕАН АзиатскоТихоокеанское экономическое сотрудничество АТЭС Асеановский региональный форум АРФ Шанхайская организация сотрудничества ШОС и др. Роль США в АТР АТР объединяет около 25 стран бассейна Тихого океана. Факторы повлиявшие на выделение АТР в особую зону мирового развития: передел мира после 2 ой мировой войны США становится лидером;...
81049. Внешняя политика Китайской народной республики 49.14 KB
  Документ подписали глава МИД КНР Ян Цзечи и министр иностранных дел России Сергей Лавров который находится в Китае с рабочим визитом. Таким образом между РФ и КНР окончательно урегулирована территориальная проблема переговоры по которой длились более 40 лет поставлена точка в пограничном размежевании между нашими странами и завершено юридическое оформление общей границы. Дополнительное соглашение между РФ и КНР о российско-китайской государственной границе на её восточной части было подписано в Пекине...
81050. Позиция РФ в Азиатско- Тихоокеанском регионе. Китай. Япония 53.61 KB
  Более 70 внешнеторгового оборота России с азиатскими странами приходится на государства АзиатскоТихоокеанского региона АТР. Наиболее крупными торговыми партнерами России в регионе являются Китай Япония и Республика Корея Южная Корея. Этот процесс завершил урегулирование пограничных проблем в отношениях России и КНР многолетний переговорный процесс который был начат ещё СССР и КНР в 1964 и который помимо переговоров дипломатов сопровождался ещё и кровопролитием с обеих сторон. В отношениях России с КНР важнейшей задачей на ближайшее...
81051. Многосторонние международные институты и международные организации в современных международных отношениях 41.21 KB
  Международные правительственные организации МПО членами которых выступают национальные правительства и которые создаются посредством заключения договоров между государствами. МПО выполняют роль надгосударственных образований т. МПО в зависимости от целей и членства разделяются на универсальные ООН региональные АСЕАН МЕРКОСУР ШОС и функциональные организации МАГАТЕ. В настоящее время существует свыше 300 МПО.