6229
Теорія графів. Розвязок задачі на основі графів на мові C++
Курсовая
Информатика, кибернетика и программирование
Теорія графів - це галузь дискретної математики, особливістю якої є геометричний підхід до вивчення об'єктів. Вона перебуває зараз у самому розквіті. Розділ теорії графів Зв'язність графів, що розглядається у цій роботі, є дуже актуальною на сьогоднішній день. Наприклад її прямим застосуванням є теорія сітей – та її додаток - теорія електронних сітей...
Украинкский
2013-01-03
583.5 KB
52 чел.
Вступ
Теорія графів - це галузь дискретної математики, особливістю якої є геометричний підхід до вивчення об'єктів. Вона перебуває зараз у самому розквіті. Розділ теорії графів «Звязність графів», що розглядається у цій роботі, є дуже актуальною на сьогоднішній день. Наприклад її прямим застосуванням є теорія сітей та її додаток - теорія електронних сітей, що активно використовуються у компютерних мережах сьогодення.
У цій роботі розглядається розвязок задачі, основою якої є граф. Робота поділена на чотири частини, що у свою чергу включають в себе підпункти, висновок, список використаної літератури та додаток (текст програми на мові C++).
У першому розділі ми розглядаємо текст задачі й аналізуємо його саме щодо теорії графів.
У другому пункті, що поділений на дві частини розглядається докладно метод вирішення задачі й алгоритм написання програми на мові C++.
Третя частина розділена на три підпункти: інструкція користувача, розрахунок контрольних прикладів й аналіз результатів. Розрахунок контрольних прикладів означає рішення прикладів, подібних нашій задачі без використання програми й за допомогою неї. В той час як аналіз результатів полягає у тому, що ми повинні визначити залежність швидкості програми від розміру графу.
Останній, четвертий, розділ включає в себе приклади практичного застосування даної програми.
Тобто ця курсова робота є повним розвязком задачі, що і є метою створення даної праці.
На олімпіаду прибуло N людей. Деякі з них знайомі між собою. Чи можливо опосередковано перезнайомити їх усіх між собою? (Незнайомі люди можуть познайомитися лише через спільного знайомого).
Постановка задачі у термінах теорії графів.
Сформулюємо умову задачі в термінах теорії графів. Нехай кожному учаснику відповідає вершина графа. Тоді той факт, що два учасника знайомі між собою зобразимо у вигляді ребра, що зєднує відповідні їм вершини. Можливість опосередковано познайомити двох учасників означає, що у графі існує шлях між відповідними вершинами. Можливість познайомити усіх учасників означає існування шляху між будь-якими двома вершинами графа. Такі графи називаються звязними. Тобто ми повинні перевірити граф на звязність.
Нехай 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
Таблиця змінних
Данні |
Тип данних |
Описання |
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] чи ні |
Для реалізації цієї задачі була створена програма мовою С++. Вона є досить легка у використанні. З початку необхідно знайти файл з назвою 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. Вирішення задачі вручну. Початкові данні: 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 |
Виконуємо такі дії:
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 |
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 |
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 |
№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
Аналіз результатів полягає у вимірюванні швидкості роботи представленої програми та її залежності від розміру обробляємої інформації. У ході визначення цієї величини я прийшла до висновку, що швидкість програми ніяк не залежить від розміру графу, бо, якої б розмірності граф я не використовувала, час початку роботи програми та час її закінчення кожного разу збігався.
За допомогою цієї програми можно не тільки визначати, чи можливо перезнайомити усіх людей між собою через спільних знайомих. Даний метод можна також використовувати:
ВИСНОВОК
У процесі проведеної роботи ми:
Виходячи з цих пунктів можна сказати, що була проведена результативна й корисна для спільноти праця.
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
ДОДАТОК
#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
А также другие работы, которые могут Вас заинтересовать | |||
36974. | Dивчення засобів роботи з масивами в C++ | 71.5 KB | |
Практичне засвоєння методів обробки інформації із застосуванням масивів. Завдання 9-1. Скласти й відлагодити програму, яка створює (в пам’яті ЕОМ) квадратну матрицю порядка n (n задавати константою). | |||
36975. | Дослідження параметрів зворотноосмотичної системи очищення водопровідної води | 99 KB | |
В даному випадку мембрана проникна для води і непроникна для солі тому вода може проходити через мембрану в обох напрямках а сіль не може. В звязку із тим що зворотний перетік відсутній в частині посудини із чистою водою рівень рідини буде зменшуватись а в частині із сольовим розчином збільшуватись до тих пір доки тиск водяного стовпа надлишок над рівнем рідини в частині з чистою водою зросте настільки що сила його буде стримувати перетік води. Якщо в частині із сольовим розчином створити тиск який перевищує осмотичний то... | |||
36976. | Призначення та основні технічні характеристики гірокомпаса Круїз | 78.24 KB | |
Прилад ЦП01 є центральним приладом ГК Круїз і складається з гіростабілізованої платформи з ДНГ і акселерометром у кардановому підвісі елементів слідкуючої системи і системи керування ДНГ. Основним ЧЕ розглянутого ГК є динамічно настроюваний гіроскоп ДНГ.1 подана спрощена схема ДНГ.за допомогою внутрішнього карданового підвісу з валом 2 привідного електродвигуна 3 статор якого закріплений у корпусі ДНГ показаному на рисунку пунктирною лінією. | |||
36977. | Дослідження впливу вмісту солей у вхідному розчині та тиску на мембрану на параметри зворотноосмотичної системи опріснення морської води | 325.03 KB | |
Вхідний водний розчин солі із місткості 1 подається на передфільтр 2 де відбувається первинна очистка його. приготувати 10 л водного розчину солі NCl із концентрацієюСвх = 1 або 10000 мг л 10 г солі на 1 л води; залити розчин солі в місткість для вхідної рідини; підготувати до функціонування блок вимірювання електричноїпотужності; включити установку в мережу електроживлення через блоквимірювання електричної потужності.5 хв зробити бажано одночасно заміри... | |||
36978. | Встановлення і налаштування веб-сервера (Windows, Linux) | 1.27 MB | |
Встановлення IIS Windows У Windows 2000 Server компонент IIS встановлювався за замовчуванням. У WS03 необхідно інсталювати IIS вручну згідно нової концепції Microsoft Вимкнено за замовчуванням . IIS більше не є частиною установки за замовчуванням. Нижче наведено основні кроки при встановленні IIS: В Control Pnel Панель управління клацніть на значкуdd or Remove Progrms Установка і видалення програм для відкриття діалогового вікна. | |||
36979. | Дослідження процесу розробки класів програмними засобами для різних задач | 14.3 KB | |
Розробіть класи для задачі про філософів що обідають. Розробіть класи для підписки на журнали. Розробіть класи для редактора графічних документів що підтримують групування обєктів. | |||
36980. | ПОВІРКА ВОЛЬТМЕТРА УНІВЕРСАЛЬНОГО В7-16 ТА ПРЯМЕ ВИМІРЮВАННЯ ОПОРУ РЕЗИСТОРА | 226.5 KB | |
ПРИЗНАЧЕННЯ Вольтметр універсальний В716 призначений для автоматичного виміру: напруги постійного струму; напруги змінного струму; активних опорів. У вхідному пристрої напруга постійного струму приводиться за допомогою дільника до номінальної межі і далі надходить на вхід підсилювача диференційного напруга змінного струму приводиться до номінальної межі і надходить на перетворювач напруги змінного струму в напругу постійного струму а потім на вхід підсилювача диференційного. Другий каскад разом з першим забезпечує загальний... | |||
36981. | ВИБІР СИСТЕМИ ТРУДОВОГО та професійного НАВЧАННЯ | 89 KB | |
Методика трудового та професійного навчання частина І. Проектнотехнологічна система трудового навчання Трудова підготовка в закладах освіти. Формування загально трудових умінь у різних дидактичних системах трудового навчання Трудова підготовка в закладах освіти. | |||
36982. | Побудова FTP-сервера на основі операційної системи Linux | 526 KB | |
Він розташований в каталозі etc і має ім'я proftpp. Також можуть знадобитися команди: виклик редактора mcedit робота з FTPсервером ftp визначення IPадреси ifconfig тестування каналу ping запуск файлового провідника mc допомога mn [команда] Алгоритм налаштування FTPсервера наступний: 1 Встановити пакет proftpd за допомогою команди sudoptitude instll proftpd. Якщо FTPсервер не використовуватиметься постійно... | |||