Основи дискретної математики

Міністерство освіти і науки, молоді та спорту України

Полтавський національний технічний університет імені Юрія Кондратюка

Факультет інформаційних та телекомунікаційних технологій і систем

Кафедра компютерних та інформаційних технологій і систем

Розрахунково-графічна робота

З дисципліни

«Система компютерної математики»

Виконав:

студент групи 101ТН

Соколов К.А.

Перевірила:

Гафіяк А. М.

Полтава 2012

Міністерство освіти і науки, молоді та спорту України

Полтавський національний технічний університет імені Юрія Кондратюка

факультет інформаційних та телекомунікаційних технологій і систем

кафедра компютерних та інформаційних технологій і систем

ЗАВДАННЯ

до розрахунково-графічної роботи

Група: 101-ТН Студент: Соколов К. А. .Керівник: Бородіна О.О.

Завдання 1. Задано матрицю суміжності графа.

0100010201020010000001101

Завдання 1.1. Побудувати граф, що відповідає їй.

Завдання 1.2. Побудувати множину пар вершин, що відповідає їй.

Завдання 1.3. Знайти кількість вершин, ребер (дуг) і степені (напівстепені) кожної вершини графу.

Завдання 1.4. Побудувати матрицю інцидентності графа.

Завдання 1.5. Побудувати граф, ізоморфний заданому.

Завдання 1.6. Чи існує Ейлерів цикл та шлях у графі?

Завдання 1.7. Чи існує Гамільтонів цикл та шлях у графі?

Завдання 1.8. Перетворити граф у зважений (ваги визначити самостійно) та за допомогою алгоритму Дейкстри знайти довжину найкоротшого шляху між двома вершинами (обрати самостійно) та побудувати цей шлях.

Завдання 1.9. Побудувати простий граф (n=5), розфарбувати

його та визначити його хроматичне число ? .

Завдання 2. Задано дерево.

Завдання 2.1. Визначити корінь дерева, його батьків, синів, листки. Які вершини є внутрішніми?

Завдання 2.2. Визначити рівень кожної вершини та висоту дерева.

Завдання 2.3. Чи є дерево завершеним?

Завдання 2.4. Чи є дерево збалансованим?

Завдання 2.5. Виконати обхід дерева у прямому, внутрішньому та зворотному порядках.

Завдання 2.6. Визначити ексцентриситет вершин та центр дерева.

граф матриця дерево вершина

Зміст звіту по роботі: титульний аркуш, бланк завдання, зміст, вступ, розвязок завдань із детальним поясненням, висновки, список літератури.

Додаткове завдання: Побудувати блок-схему алгоритму задачі. Реалізувати отриманий алгоритм у певному середовищі програмування.

ВСТУП

Дискретна математика - область математики, що вивчає властивості дискретних структур, які виникають як в межах самої математики, так і в її застосуваннях. До таких структур можуть бути віднесені скінченні групи, скінченні графи, а також деякі математичні моделі перетворювачів інформації, скінченні автомати, машини Тьюринга і так далі. Це приклади структур скінченного характеру. Розділ дискретної математики, що вивчає їх, називається скінченною математикою. Іноді само це поняття розширюють до дискретної математики. Крім вказаних скінченних структур, дискретна математика вивчає деякі системи алгебри, нескінченні графи, обчислювальні схеми певного вигляду, клітинні автомати і т. д. Як синонім іноді уживається термін «дискретний аналіз».

Властивості дискретних структур: - скінченні структури; - скінченні графи; - деякі математичні моделі перетворювачів інформації; - скінченні автомати; - машини Тьюринга; ...

Дискретність - це перервність.

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

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

В документах UNESCO вказується, що потрібен перегляд всієї системи вивчення математичних наук з посиленням ролі дискретної математики.

РОЗВЯЗАННЯ

Завдання 1

Задано матрицю суміжності графа

0100010201020010000001101

Завдання 1.1

Побудувати граф.

Завдання 1.2

Е={(V1,V2),(V2,V5),(V2,V3),(V2,V3),(V5,V5),(V3,V5)}

Завдання 1.3

(V,E)=5 - вершини=6 - ребра(V1)=1(V2)=4(V3)=3(V4)=0(V5)=4

Завдання 1.4

Створюємо матрицю інцидентності графа. Матриця буде не булевою оскільки на вершині V5 петля.

E1E2E3E4E5E6V1100000V2111100V3011010V4000000V5000112

Завдання 1.5

Будуємо граф ізоморфний даному.

Завдання 1.6

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

Завдання 1.7

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

Завдання 1.8

Задаємо графу довільні ваги, тобто утворюємо зважений граф. Та знайдемо найкоротший шлях з вершини V1 до вершини V2.

)Почнемо з вершини V1, відстань до всіх інших вершин ?, а до даної вершини 0.

)Оскільки інує тільки одне ребро інцидентне V1 , то далі йдемо до вершини V2 з вагою ребра , зєднуючого ці вершини 3.

)З V2 йдемо до вершини V5 тому, що вага ребра ведучого до V5 найменша (4<7<8).

)З V5 йдемо до V3 з вагою 2 і отримаємо 3+4+2=9 - найкоротший шлях до вершини V3 за алгоритмом Дейкстри.

Завдання 1.9

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

Хроматичне число ? - це найменша можлива кількість кольорів застосованих при розфарбуванні графа.

Для даного графа ?(G)=3

Завдання 2

Дано дерево

Завдання 2.1

Корінь - a

Сини - b, c

Листки - d, e, k ,l, m, q, r, s, u, v,p

Внутрішні вершини - a, b, c, f, g, h, i, j, n, o, t

Завдання 2.2

-ий рівень,c-I рівень, e, f, g-II рівень, i, j-III рівень, l, m, n, o, p-IV рівень, r, s, t-V рівень, v-VI рівень

Висота дерева h=5

Завдання 2.3

Завершеним називають дерево у якого всі листки на одному рівні. Дане дерево не являється завершеним.

Завдання 2.4

Збалансованим деревом висотою h називають дерево, якщо всі його листки розташовані на рівнях h-1 та h. Дане дерево не являється збалансованим.

Завдання 2.5

)Обхід у прямому порядку

)Обхід у внутрішньому порядку.

) Обхід у зворотному порядку

Завдання 2.6

Ес(х)-ексцентриситет вершини х- максимальна відстань від даної вершини до всіх інших вершин (вимірюється в кількості ребер).

Ес(a)=6

Ес(b)=7

Ес(c)=5

Ес(d)=8diametr = 8

Ес(e)=8radius = 4

Ес(f)=6центр дерева у вершині g

Ес(g)=4

Ес(h)=7

Ес(i)=5

Ес(j)=5

Ес(k)=8

Ес(l)=8

Ес(m)=8

Ес(n)=6

Ес(o)=6

Ес(p)=6

Ес(q)=7

Ес(r)=7

Ес(s)=7

Ес(t)=7

Ес(u)=8

Ес(v)=8

ВИСНОВКИ

) Методи дискретної математики дозволяють вирішувати складні задачі комбінаторики та математичного аналізу.

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

) Завдяки методам відомих вчених в області теорії графів було вирішено багато досить цікавих та корисних для суспільства задач.

)Задачі з дискретної математики дуже добре розвивають логіку мислення та інтелект.

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

1)«Дискретна математика» С.Лукяненко. К-2000

)«Комбінаторика» Д.Сафонов. М-1992

)«Дискретна математика» Ю.В. Нікольський

)Конспект лекцій

)Компютерна мережа Інтернет