Печать: Ctrl+P → ориентация альбомная, масштаб 100 % (не «вписать в лист»), поля нет, «печать фона» включить — иначе пропадут рамки таблиц. На листе две одинаковые карточки: разрезать по пунктиру посередине, получится две штуки формата A5. Эта серая рамка на бумагу не печатается.
11 класс

Графы: представление, кратчайший путь, число путей

Обзорный практикум по содержанию ФГОС к седьмой паре 11 класса

Основные понятия

Граф — вершины и связи между ними. Связь без направления — ребро (неориентированный граф), со стрелкой — дуга (ориентированный). Если у связей есть числа (длина, цена, время), граф взвешенный. Степень вершины — сколько рёбер из неё выходит.

Как граф записывают

  • матрица смежности — таблица n × n, 1 в клетке: вершины связаны. У неориентированного графа она симметрична, каждое ребро записано дважды: рёбер = единиц : 2;
  • весовая матрица — в клетке вес связи, пустая клетка — связи нет;
  • списки смежности — у каждой вершины перечислены соседи: А → Б, В. У ориентированного графа строка вершины — это выходящие дуги; входящие ищут по всем остальным спискам.

Виды графов

  • полный граф — каждая вершина соединена с каждой: n · (n − 1) : 2 рёбер;
  • дерево — связный граф без циклов: ровно n − 1 рёбер. Связный граф с m рёбрами становится деревом после удаления m − n + 1 рёбер.

Кратчайший путь (алгоритм Дейкстры)

  1. у начальной вершины расстояние 0, у остальных — «не известно»;
  2. взять ближайшую ещё не закреплённую вершину и закрепить её;
  3. для каждого её соседа: если путь через неё короче записанного — записать новое расстояние;
  4. повторять, пока не закреплена нужная вершина.

Прямая дорога не обязательно самая короткая — обход через другие пункты бывает выгоднее.

Число путей в графе без циклов

Идти по вершинам от начальной: в начальную ведёт 1 путь, а в любую другую — сумма путей во все вершины, из которых в неё есть дуга.

что спрашиваюткак считать
через вершину X(пути до X) · (пути от X до конца)
в обход Xвычеркнуть X со всеми дугами и пересчитать
Тренажёр и разбор темы: https://kibersvet.ru/11/grafy/
Материалы подготовлены с использованием технологий искусственного интеллекта.
11 класс

Графы: представление, кратчайший путь, число путей

Обзорный практикум по содержанию ФГОС к седьмой паре 11 класса

Основные понятия

Граф — вершины и связи между ними. Связь без направления — ребро (неориентированный граф), со стрелкой — дуга (ориентированный). Если у связей есть числа (длина, цена, время), граф взвешенный. Степень вершины — сколько рёбер из неё выходит.

Как граф записывают

  • матрица смежности — таблица n × n, 1 в клетке: вершины связаны. У неориентированного графа она симметрична, каждое ребро записано дважды: рёбер = единиц : 2;
  • весовая матрица — в клетке вес связи, пустая клетка — связи нет;
  • списки смежности — у каждой вершины перечислены соседи: А → Б, В. У ориентированного графа строка вершины — это выходящие дуги; входящие ищут по всем остальным спискам.

Виды графов

  • полный граф — каждая вершина соединена с каждой: n · (n − 1) : 2 рёбер;
  • дерево — связный граф без циклов: ровно n − 1 рёбер. Связный граф с m рёбрами становится деревом после удаления m − n + 1 рёбер.

Кратчайший путь (алгоритм Дейкстры)

  1. у начальной вершины расстояние 0, у остальных — «не известно»;
  2. взять ближайшую ещё не закреплённую вершину и закрепить её;
  3. для каждого её соседа: если путь через неё короче записанного — записать новое расстояние;
  4. повторять, пока не закреплена нужная вершина.

Прямая дорога не обязательно самая короткая — обход через другие пункты бывает выгоднее.

Число путей в графе без циклов

Идти по вершинам от начальной: в начальную ведёт 1 путь, а в любую другую — сумма путей во все вершины, из которых в неё есть дуга.

что спрашиваюткак считать
через вершину X(пути до X) · (пути от X до конца)
в обход Xвычеркнуть X со всеми дугами и пересчитать