Міністерство освіти та науки України
Дніпропетровський національний університет ім. О.Гончара
Економічний факультет
Кафедра економічної кібернетики
Курсова робота
з дисципліни:
«Управління інформаційними ресурсами»
Дніпропетровськ
2010 р.
ЗМІСТ
Вступ
Постановка задачі.............................................................................................4
Метод вирішення..............................................................................................5
Метод вирішення………………………………………………………5
Алгоритм вирішення задачі..................................................................7
Програмне забезпечення вирішення задачі.................................................9
Інструкція користувача..........................................................................9
Розрахунок контрольних прикладів………………………...………12
Аналіз результатів…………………………………………………..16
Практичне застосування...........................................................................17
Висновок
Список використаної літератури
Додаток
ВСТУП
Теорія графів - це галузь дискретної математики, особливістю якої є геометричний підхід до вивчення об'єктів. Вона перебуває зараз у самому розквіті. Розділ теорії графів «Зв’язність графів», що розглядається у цій роботі, є дуже актуальною на сьогоднішній день. Наприклад її прямим застосуванням є теорія сітей – та її додаток - теорія електронних сітей, що активно використовуються у комп’ютерних мережах сьогодення.
У цій роботі розглядається розв’язок задачі, основою якої є граф. Робота поділена на чотири частини, що у свою чергу включають в себе підпункти, висновок, список використаної літератури та додаток (текст програми на мові 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.