Россия, Кузнецк
СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ
Благодаря готовым учебным материалам для работы в классе и дистанционно
Скидки до 50 % на комплекты
только до
Готовые ключевые этапы урока всегда будут у вас под рукой
Организационный момент
Проверка знаний
Объяснение материала
Закрепление изученного
Итоги урока
Была в сети 13.08.2025 09:44
Коткова Наталья Геннадьевна
преподаватель математических дисциплин и информатики
47 лет
23 251
1 437 
Местоположение
Специализация
Способы задания графов
Категория:
Математика
19.06.2025 16:03
Просмотр содержимого документа
«Способы задания графов»
Тема «Способы задания графов»
План лекции:
Реализация графов
Задание матрицей инцидентности
Задание матрицей смежности
Перечислением списком смежности
Задание матрицей расстояний
Реализация графов
Человеку удобно работать с графом – рисунком (схемой, диаграммой), так как он может легко установить связь между вершинами в наглядном виде с помощью ребер. Такое геометрическое представление плоского графа называется его реализацией.
Для машинной обработки удобнее задать граф в алгебраической форме – перечислением (списком) ребер и вершин. Но с таким представлением ЭВМ трудно работать, так как для указания каждого ребра нужно еще раз выписывать соответствующую вершину, что плохо с точки зрения сжатия и хранения информации. Иногда граф задается таблицей, состоящей из 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 |
Самостоятельная работа студентов
Переписать лекцию в тетрадь и прислать фото
Составить для неориентированного графа G2 матрицу инцидентности
Составить для ориентированного графа G1 матрицу смежности
Построить матрицу расстояний и список смежности для следующих графов:
Это ориентированный граф. В вершине 3 петля, добавьте стрелочку. Граф перерисовать.
Это неориентированный граф. Граф перерисовать.
Вебинар для учителей
Свидетельство об участии БЕСПЛАТНО!
