рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Логічна структура, визначення

Реферат Курсовая Конспект

Выберите учебное заведение

Логічна структура, визначення

Логічна структура, визначення - раздел Образование, Графи P Граф - Це Складна Нелінійна Багатозв’Язна Динамічна Структура...

Граф - це складна нелінійна багатозв’язна динамічна структура, що відображає властивості і зв'язки складного об'єкта і має наступні властивості:

- на кожен елемент (вузол, вершину) може бути довільна кількість посилань;

- кожен елемент може мати зв'язок з будь-якою кількістю інших елементів;

- кожне зв'язування (ребро, дуга) може мати напрямок і вагу.

У вузлах графа утримується інформація про елементи об'єкта. Зв'язки між вузлами задаються ребрами графа. Ребра можуть мати спрямованість, показувану стрілками, тоді вони називаються орієнтованими. Коли ребра без стрілок - неорієнтовані. Граф, усі зв'язки якого орієнтовані, називається орієнтованимграфом або орграфом; граф із усіма неорієнтованими зв'язками - неорієнтованим графом; граф зі зв'язками обох типів - змішаним графом. Позначення зв'язків: неорієнтованих - (A,B), орієнтованих - <A,B>.

Приклади зображень графів дані на рис.7.5. Скобкове представлення графів: а). (<A,B>,<B,A>) та б). ((A,B),(B,A)).

Рис.7.5. Зображення графа

а) – орієнтований,

б) - неорієнтований

Для орієнтованого графа число ребер, що входять у вузол, називається напівступенем заходу вузла, що виходять з вузла - ступенем виходу. Кількість вхідних і вихідних ребер може бути будь-яким, у тому числі і нульовим. Граф без ребер є нуль-графом. Якщо ребрам графа відповідають деякі значення, то граф і ребра називаються зваженими. Мультиграфом називається граф, що має паралельні ребра (що з'єднують ті самі вершини), у противному випадку граф називається простим.

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

Матрицею суміжності для n вузлів називається квадратна матриця adj порядку n. Елемент матриці a(i,j) дорівнює 1, якщо вузол j суміжний з вузлом i (є шлях <i,j>), і 0 - у противному випадку. Якщо граф неорієнтований, то a(і,j)=a(j,і), як наслідок, матриця суміжності буде симетрична щодо головної діагоналі.

Матриці суміжності використовуються при побудові матриць шляхів, що дають представлення про граф по довжині шляху: шлях довжиною в 1 - суміжну ділянку <A,B>, шлях довжиною 2 - (<A,B>,<B,C>), ... у n суміжних ділянок: де n - максимальна довжина, що дорівнює числу вузлів графа.

На рис. 7.7 дані шляхові матриці шляху adj1, adj2, adj3, adj4 для графа рис. 7.6.

Рис.7.6. Граф

	(A)(B)(C)(D)		(A)(B)(C)(D)		(A)(B)(C)(D)		(A)(B)(C)(D)
(A) (B) (C) (D)	0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0	(A) (B) (C) (D)	0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1	(A) (B) (C) (D)	1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1	(A) (B) (C) (D)	1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1

adj1 adj2 adj3 adj4

Рис.7.7. Матриці шляхів

На рис. 7.8 показана матриця інцидентності для графа рис. 7.5.

Вузли/номера зв'язків 1 2

A B -

B C D

C D -

D A C

Рис.7.8. Матриця інцидентності

Матриці інцидентності використовуються тільки для орграфів. У кожнім рядку записується упорядкована послідовність імен вузлів, з якими даний вузол зв'язаний ориєнтованими (вихідними) ребрами.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Графи P

ДИНАМІЧНІ СТРУКТУРИ ДАНИХ R... Особливості динамічних структурP Лінійні зв язні списки P...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Логічна структура, визначення

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Особливості динамічних структур
Динамічні структури даних по визначенню характеризуються: Ø відсутністю фізичної суміжності елементів структури в пам'яті, Ø мінливістю і непередбачу

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

Застосування лінійних списків
Лінійні списки знаходять широке застосування в додатках, де непередбачені вимоги на розмір пам'яті, необхідної для збереження даних; велике число складних операцій над даними, особливо операцій

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

Застосування списків
Найбільше впровадження списки знайшли у мові програмування LISP. LISP – це мова обробки списків. Усі дані в LISP представляються у вигляді списків, структура елемента списку включає

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

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

Основні визначення
Дерево - це граф, що характеризується наступними властивостями: - існує єдиний елемент (вузол, вершина), на який не посилається ніякий інший елемент - який називається корене

Логічне представлення і зображення дерев
Мається ряд способів графічного зображення дерев (див. рис. 7.17). 1). Використання діаграм Венна, що наочно показують вкладеність піддерев. 2). Спосіб,

Бінарні дерева
Відрізняють m-арні дерева, тобто такі дерева в яких напівступінь виходу кожної вершини менше або дорівнює m (де m може дорівнювати 0,1,2,3 і т.д.). Якщо напівступінь виходу кожної вершини в точн

Типи бінарних дерев
Очевидно, що дерева, що складаються з n вершин, можуть бути побудовані по-різному. У залежності від того, як будуються дерева, розрізняють: ідеально збалансовані дерева, збалансовані і не збалан

Основні операції над деревами
Над деревами визначені наступні основні операції: - обхід дерева у визначеному порядку, - пошук вузла з заданим ключем, - додавання нового вузла, - видалення вуз

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