Элементы теории графов

• Граф — это один из способов графического представления информации, отражающий количество объектов изучаемой системы и взаимосвязи между ними.

Вершины и рёбра графа
Граф состоит из вершин (узлов), связанных дугами или рёбрами. Вершины изображают точками, кругами, овалами, прямоугольниками и т.д.
Связи между вершинами называют ветвями и изображают линиями. Если линия направленная, т.е. со стрелкой, она называется дугой. Если линия ненаправленная, т.е. без стрелок, она называется ребром. Дуги могут пересекаться, но точки пересечения не являются вершинами графа.
Количество вершин графа называют его порядком. Количество рёбер называют размером графа.
Взвешенный граф
Рёбрам графа могут быть сопоставлены числовые значения, которые называют весами рёбер. Например, вес ребра в графе, обозначающем дорожную сеть, может представлять собой длину соответствующей дороги между вершинами графа, обозначающими населённые пункты.

• Взвешенный граф — это граф, рёбрам которого назначены значения весов.

Мультиграф
Две вершины называют концевыми вершинами (концами) ребра, которое их соединяет. При этом говорят, что ребро инцидентно каждой из соединяемых им вершин, и наоборот, каждая концевая вершина называется инцидентной соединяющему их ребру. Две концевые вершины одного и того же ребра называют соседними.
Рёбра, имеющие общую концевую вершину, называют смежными. Рёбра, инцидентные одной и той же паре вершин (т.е. соединяющие одну и ту же пару вершин) называют кратными, или параллельными.

• Мультиграф — это граф с кратными рёбрами.

Псевдограф
Ребро, концами которого является одна и та же вершина, называется петлёй.

• Псевдограф — это граф , содержащий петли (и кратные рёбра).

Ещё немного о вершинах

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

Вершина называется изолированной, если она не является концом ни для одного ребра. Вершина называется висячей (листом), если она является концом ровно одного ребра.

• Пустой граф — это граф, состоящий из произвольного количества изолированных вершин (т.е. не имеющий рёбер).
• Полный граф — это граф, не имеющий петель и кратных рёбер, в котором каждая пара вершин соединена ребром.

Путь в графе

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

Циклом называют путь, в котором первая и последняя вершины совпадают. Путь (или цикл) называют простым, если рёбра в нём не повторяются. Простой путь (цикл) называют элементарным, если вершины в нём не повторяются.
Длиной пути (или цикла) называют количество составляющих его рёбер.

• Связный граф — это граф, в котором для любых двух вершин существует связывающий их путь.
• Сильно связный граф — это ориентированный граф, в котором существует маршрут из любой вершины в любую другую.

Неориентированный и ориентированный граф
В неориентированном графе связи между любыми парами концевых вершин являются двунаправленными, т.е. эти концевые вершины «равноправны» по отношению к этой связи.
В ориентированном графе связи между концевыми вершинами являются направленными. Рёбра ориентированного графа называют дугами. Пути в ориентированном графе называют ориентированными путями (маршрутами). Замкнутый путь (цикл) в ориентированном графе называют контуром.

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

Полный направленный граф называют турниром.

• Обратный граф — это ориентированный граф, полученный из исходного путём смены направлений рёбер на противоположные.

Способы представления графов
1. Графический способ — изображение графа.
2. Список рёбер — перечисление всех рёбер графа как пар обозначений связываемых этими рёбрами вершин. Пример: {A, B}, {A, D}, {A, C}, {B, C}, {C, D}.
3. Матрица смежности — квадратная симметричная таблица (матрица), в которой и столбцы, и строки соответствуют вершинам графа, а в ячейках на их пересечении записываются числа, обозначающие наличие или отсутствие связей между соответствующими парами вершин (обычно – количество связей между вершинами).
В простейшем случае, когда граф не имеет кратных рёбер и петель, матрица смежности содержит единицы для ячеек, соответствующих парам вершин, связанных ребром, и нули – для несвязанных вершин.
Для взвешенного графа возможен вариант матрицы смежности, где в ячейках записываются веса рёбер или нули (либо ячейки оставляются пустыми).
4. Матрица инцидентности — таблица, столбцы которой соответствуют вершинам, а строки – рёбрам. При этом в ячейках на их пересечении записываются числа:

• для неориентированного графа – число 1, если данная вершина инцидентна данному ребру, или 0 – в противном случае;
• для ориентированного графа – число -1, если данная дуга исходит из данной вершины, число 1, если данная дуга входит в данную вершину, число 2, если дуга представляет собой петлю, или 0 – в противном случае.
• Источник: https://ctege.info/informatika-teoriya-ege/zadanie-1-ege-po-informatike.html
• Источник: https://ctege.info/informatika-teoriya-ege/zadanie-1-ege-po-informatike.html

Алгоритмы, виды алгоритмов, описание алгоритмов. Формальное исполнение алгоритмов


Алгоритм – это точно сформулированное исполнителю предписание совершить определенную последовательность действий для решения задачи за конечное число шагов.

Построение таблиц истинности логических выражений

Решить логическое выражение методом заполнения таблицы истинности

Объяснение задания 2 ЕГЭ по информатике

Разбор 2 задания из ЕГЭ по информатике 2023


Разбор 2 задания ЕГЭ по информатике решение в EXCEL (2019 вариант 4, Крылов С.С., Чуркина)



ВСЕ ТИПЫ 2 заданий | Информатика ЕГЭ 2023 | Виктория Ланская | Умскул



ЗАДАНИЕ №2 за 129 СЕКУНД на Python // ЕГЭ информатика 2023


2 задание на Python. Информатика ЕГЭ 2021

Информатика ЕГЭ 2023 | Задание 2 | Сложное просто
Шаблон задания № 2

Пошаговый разбор задания №2

ЕГЭ Информатика 2022. Excel и его безграничные возможности
Научим решать № 2, 5, 9, 12, 15, 16, 17, 18, 23 из ЕГЭ по информатике с помощью Excel с НУЛЯ.

Функции Excel для ЕГЭ

Объяснение заданий 3 ЕГЭ по информатике

Решение задания №3. Демоверсия ЕГЭ по информатике - 2023

Видео Иван Викторович Задание № 3

Устный разбор

Тренажер по заданию № 3