СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до 17.07.2025

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

Способы задания графов

Категория: Математика

Нажмите, чтобы узнать подробности

Лекция на на заданную тему по предмету "Дискретная математика" для студентов специальностей 09.02.

Просмотр содержимого документа
«Способы задания графов»

Тема «Способы задания графов»

План лекции:

  1. Реализация графов

  2. Задание матрицей инцидентности

  3. Задание матрицей смежности

  4. Перечислением списком смежности

  5. Задание матрицей расстояний



Реализация графов

Человеку удобно работать с графом – рисунком (схемой, диаграммой), так как он может легко установить связь между вершинами в наглядном виде с помощью ребер. Такое геометрическое представление плоского графа называется его реализацией.

Для машинной обработки удобнее задать граф в алгебраической форме – перечислением (списком) ребер и вершин. Но с таким представлением ЭВМ трудно работать, так как для указания каждого ребра нужно еще раз выписывать соответствующую вершину, что плохо с точки зрения сжатия и хранения информации. Иногда граф задается таблицей, состоящей из n строк – вершины, m столбцов – ребер.

Реализация графа – это графическое представление графа.

Способы задания графов:

  • Матрицей инцидентности (таблица);

  • Матрицей смежности (таблица);

  • Списком смежности (перечисление);

  • Матрицей расстояний (таблица).



Задание матрицей инцидентности

МАТРИЦЕЙ ИНЦИДЕНТНОСТИ графа G(V,X) называют прямоугольную матрицу, состоящую из n строк (количество вершин) и m столбцов (количество ребер), в которой:

ДЛЯ НЕОРИЕНТИРОВАННОГО ГРАФА:

ДЛЯ ОРИЕНТИРОВАННОГО ГРАФА:






Пример: составить для ориентированного графа G1 матрицу инцидентности


r

s

t

u

G1

A

1

-1

0

0

B

-1

0

1

1

C

0

1

-1

-1



Задание матрицей смежности


МАТРИЦЕЙ СМЕЖНОСТИ НЕОРИЕНТИРОВАННОГО ГРАФА G(V,X) БЕЗ КРАТНЫХ РЕБЕР называют квадратную матрицу порядка n (количество вершин), в которой:

ДЛЯ ОРИЕНТИРОВАННОГО ГРАФА:

Пример: составить для неориентированного графа G2 матрицу смежности


A

B

C

D

E

G2

A

0

1

1

0

0

B

1

0

0

1

0

C

1

0

0

1

0

D

0

1

1

0

0

E

0

0

0

0

0

Перечислением списком смежности

Список смежности – это список для каждой вершины, в котором отображаются только те, вершины, которые смежные данной.

Пример из предыдущих пунктов,


Список смежности для графа G1 выглядит следующим образом: LA: B, LB: C,C, LC: A.

Список смежности для графа G2 выглядит следующим образом: LA: B,C, LB: D,A, LC: A,D, LD: C,B, LE: -.


Задание матрицей расстояний

МАТРИЦЕЙ РАССТОЯНИЙ графа G(V,X) называют квадратную матрицу порядка n (количество вершин), которая заполняется наименьшим количеством ребер (дуг) находящихся между двумя вершинами (наименьший путь).


Пример: записать матрицу расстояний для графа G1


А

В

С

А

0

1

2

В

2

0

1

С

1

2

0

Пример: записать матрицу расстояний для графа G2


А

В

С

D

E

А

0

1

1

2

0

В

1

0

2

1

0

С

1

2

0

1

0

D

2

1

1

0

0

E

0

0

0

0

0




Самостоятельная работа студентов

  1. Переписать лекцию в тетрадь и прислать фото

  2. Составить для неориентированного графа G2 матрицу инцидентности

  3. Составить для ориентированного графа G1 матрицу смежности

  4. Построить матрицу расстояний и список смежности для следующих графов:

    1. Это ориентированный граф. В вершине 3 петля, добавьте стрелочку. Граф перерисовать.

    2. Это неориентированный граф. Граф перерисовать.









Скачать

Рекомендуем курсы ПК и ППК для учителей

Вебинар для учителей

Свидетельство об участии БЕСПЛАТНО!