У роботі розглядаються
- Теорія графів
- Матриця зв'язків
- Цикломатичне число
- Хроматичне число
- Матриця довжин
- Цифрова техніка
Практична робота з теорії графів та цифрової техніки
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних технологій, автоматики та метрології
Факультет:
Комп’ютерних та інформаційних технологій
Кафедра:
Кафедра теоретичної радіотехніки та радіовимірювань
Інформація про роботу
Рік:
2011
Тип роботи:
Практична робота
Предмет:
Цифрова техніка і мікропроцесори
Група:
КН-11
Коротко про документ
Про що ця робота
Документ містить практичне завдання на побудову графа за заданою матрицею зв'язків. Виконано розрахунок матриці довжин, матриці геометрії, а також цикломатичного і хроматичного чисел.
Зміст і розділи
- Побудова графа
- Матриця довжин та геометрії
- Визначення цикломатичного числа
- Визначення хроматичного числа
Для кого:Студенти технічних спеціальностей вищих навчальних закладів
Викладачі:Не вказано
Ключові поняття
графматриця зв'язківматриця довжинматриця геометріїцикломатичне числохроматичне числомультиграфвершинареброкомпонента зв'язності
Частина тексту файла (без зображень, графіків і формул):
APSOS Practice
Дано матрицю зв’язків:Завдання(1,1)(1,3)(2,3)(3,1)(0,0)1.Побудувати граф.
2.Побудувати:
матрицю довжин;
матрицю геометрії.
3.Визначити:
цикломатичне число
хроматичне числох1х2х3х4x5х103201х20132х3010х403х50
1.
EMBED PBrush
dij = |xi – xj| + |yi - yj|
gij = dij * cij
цикломатичне число визначається за формулою:
Х2
Х3
Х4
Х1
Х5
1
2
2
3
3
(G) = m – n + k,
де m – кількість ребер, n – кількість вершин, k – кількість компонент зв’язності.
(G) = 16 – 5 + 1 = 12 – для мультиграфа
(G) = 8 – 5 + 1 = 4 – для графа без кратних ребер
визначимо хроматичне число графа. Отож бачимо, що хроматичне число графа (G) = 3
Допоможи студентському архіву
Ми допомогли тобі — допоможи наступному студенту
Оголошення від адміністратора
Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!