Способи представлення графів - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Способи представлення графів. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекція 7. Графи.

Слайд 2

Описание слайда:

§1 Способи представлення графів Графічне задання – відображення графа за допомогою точок і ліній; Матриця суміжності - ефективна для насичених графів; Матриця інцидентності – ефективний для розріджених графів; Список суміжних вершин – ефективний для розріджених графів; Список ребер – ефективний для розріджених графів.

Слайд 3

Описание слайда:

1.1 Матриця суміжності Матрицею суміжності графа G , яка відповідає заданій нумерації вершин, називають булеву квадратну матрицю А з елементами аij(i,j =1,..., n,) де

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

1.2 Матриця інцидентності

Слайд 6

Описание слайда:

1.3 Список суміжних вершин Список суміжних вершин – це масив A[n], кожен елемент A[i] якого містить список вузлів суміжних з вершиною і. A= {(1,2), (1,4), (2,1), (2,3), (2,5), (2,6), (3,2), (3,4), (3,6), (4,1), (4,3), (5,2), (6,2), (6,3), (6,6)}

Слайд 7

Описание слайда:

Реалізація списку суміжних вершин на основі масивів A[n+1] та L[2m]. Реалізація списку суміжних вершин на основі масивів A[n+1] та L[2m].

Слайд 8

Описание слайда:

1.4 Список ребер Пара [u, v] відповідає ребру {u,v}, якщо граф неорієнтований, і дузі (u,v), якщо граф орієнтований. Об'єм пам'яті у випадку представлення графа списком ребер дорівнює 2т (т - кількість ребер або дуг) - це найекономніший щодо пам'яті спосіб. Недолік - велика (порядку т) кількість кроків для знаходження множини вершин, до яких ідуть ребра або дуги із заданої вершин.

Слайд 9

Описание слайда:

§2 Маршрути, ланцюги та цикли

Слайд 10

Описание слайда:

Слайд 11

Описание слайда:

Слайд 12

Описание слайда:

§3 Орієнтовані графи

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

§4 Способи задання орієнтованих графів

Слайд 15

Описание слайда:

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

§5 Маршрути, шляхи та контури орієнтованого графа Орієнтовані маршрути: в орграфі рух за маршрутом допускається лише в напрямках, зазначених стрілками. Маршрут, який не містить повторних дуг, називається шляхом, а той, що не містить повторних вершин, – простим шляхом. Замкнений шлях називається контуром, а простий замкнений шлях – простим контуром. Граф без циклів називається безконтурним, в іншому разі орграф називається контурним.