diskrete_math/razdel3_lekc1.md

## Лекционные занятия: Основные определения. Понятие изоморфизма. Ориентированные и неориентированные графы. Взвешенный граф.

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

Для начала представьте себе карту автомобильных дорог между городами. Города можно изобразить точками, а дороги между ними – линиями, соединяющими эти точки. Или рассмотрите схему метро: станции – это точки, а перегоны между станциями – линии. А теперь представьте себе компьютерную сеть: компьютеры – это устройства, а кабели или беспроводные соединения – это связи, по которым передаются данные. В социальных сетях пользователи – это точки, а отношения «дружбы» или «подписки» – это связи. Все эти примеры объединяет одна и та же математическая структура, которую называют **графом**.

### Основные определения. Неориентированные графы.

Дадим строгое определение. **Графом** называется пара множеств \( G = (V, E) \), где \( V \) – это непустое множество объектов, которые называются **вершинами** (или узлами), а \( E \) – это множество **ребер**, каждое из которых соединяет две вершины (возможно, одну и ту же). Обычно вершины обозначают буквами или числами \( v_1, v_2, \dots \), а ребра – как \( \{v_i, v_j\} \) или просто \( v_i v_j \). Важно понимать, что в таком определении ребро не имеет направления: ребро \( \{u, v\} \) и ребро \( \{v, u\} \) – это одно и то же. Такой граф называется **неориентированным**. При этом вершины считаются соединенными, если между ними есть ребро. Сами ребра на рисунках изображаются линиями без стрелок.

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

Каждая вершина в неориентированном графе обладает важной характеристикой – **степенью**. Степень вершины – это количество ребер, инцидентных этой вершине (то есть тех, у которых она является одним из концов). При подсчете степени петля обычно дает вклад 2, поскольку она соединяет вершину с самой собой, но в простых графах петель нет. Сумма степеней всех вершин в любом графе всегда равна удвоенному числу ребер, так как каждое ребро вносит вклад в степени двух своих концов. Это свойство называется леммой о рукопожатиях.

### Ориентированные графы.

Теперь представим себе другую ситуацию. Например, в социальной сети пользователь A может подписаться на пользователя B, но не обязательно наоборот. Или на карте города дороги могут быть с односторонним движением. В компьютерной сети данные могут передаваться от одного узла к другому только в определенном направлении (например, при запросе клиента к серверу). В таких случаях ребру нужно приписать направление. Так возникает понятие **ориентированного графа** (или **орграфа**).

Формально ориентированный граф задается парой \( G = (V, X) \), где \( V \) – по-прежнему множество вершин, а \( X \) – множество **дуг**. Каждая дуга представляет собой упорядоченную пару вершин \( (u, v) \), где \( u \) – **начало** дуги, а \( v \) – **конец**. На рисунке дугу изображают стрелкой, идущей от \( u \) к \( v \). Обратите внимание, что дуги \( (u, v) \) и \( (v, u) \) – это разные дуги, если только они обе не присутствуют в графе. В ориентированном графе также могут быть петли – дуги, у которых начало и конец совпадают.

В ориентированном графе для каждой вершины вводятся две характеристики: **полустепень исхода** (количество дуг, выходящих из вершины) и **полустепень захода** (количество дуг, входящих в вершину). Сумма всех полустепеней исхода равна сумме всех полустепеней захода и равна общему числу дуг. Это естественно, потому что каждая дуга имеет одно начало и один конец.

Важно понимать, что любой неориентированный граф можно превратить в ориентированный, заменив каждое ребро \( \{u, v\} \) на две противоположно направленные дуги \( (u, v) \) и \( (v, u) \). Такой процесс называется **ориентацией** графа, хотя иногда под ориентацией понимают произвольное придание направления каждому ребру, в результате чего получается орграф без кратных дуг.

### Взвешенные графы.

В реальных задачах часто недостаточно знать только наличие или отсутствие связи между вершинами. Например, в дорожной сети важно не только то, есть ли дорога между городами, но и ее длина, время в пути или стоимость проезда. В компьютерной сети может быть важна пропускная способность канала связи. Для учета таких количественных характеристик используется понятие **взвешенного графа**.

Взвешенным называется граф (как ориентированный, так и неориентированный), каждому ребру или каждой дуге которого поставлено в соответствие некоторое число – **вес**. Вес может быть любым числом: целым, действительным, положительным или даже отрицательным, в зависимости от прикладной задачи. Обычно вес обозначают функцией \( w(e) \) или \( w(u, v) \). Для неориентированного графа вес не зависит от порядка вершин: \( w(u, v) = w(v, u) \). Для ориентированного графа веса дуг \( (u, v) \) и \( (v, u) \) могут быть разными. На рисунках взвешенные графы часто изображают, подписывая веса рядом с ребрами или дугами.

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

### Понятие изоморфизма графов.

До сих пор мы говорили о графах как о наборах вершин и ребер, которые можно рисовать на плоскости. Однако один и тот же граф можно изобразить совершенно по-разному: расположить вершины в другом порядке, искривить ребра, переименовать вершины. Возникает естественный вопрос: как определить, что два графа, нарисованные по-разному, представляют одну и ту же структуру? Для этого вводится понятие **изоморфизма графов**.

Представьте, что у вас есть два графа \( G = (V, E) \) и \( H = (W, F) \). Говорят, что эти графы **изоморфны**, если существует взаимно однозначное соответствие (биекция) \( f: V \to W \) между вершинами этих графов, которое сохраняет отношение смежности. Для неориентированных графов это означает, что две вершины \( u \) и \( v \) в графе \( G \) соединены ребром тогда и только тогда, когда их образы \( f(u) \) и \( f(v) \) соединены ребром в графе \( H \). Для ориентированных графов условие формулируется так: существует дуга из \( u \) в \( v \) в графе \( G \) тогда и только тогда, когда существует дуга из \( f(u) \) в \( f(v) \) в графе \( H \). Если графы взвешенные, то дополнительно требуется совпадение весов соответствующих ребер.

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

Как на практике определить, изоморфны два графа или нет? Иногда это можно сделать, перебирая возможные отображения, но для больших графов такой перебор невозможен из-за комбинаторного взрыва. Поэтому используют **инварианты изоморфизма** – характеристики графа, которые сохраняются при изоморфизме. Если для двух графов эти характеристики различаются, то графы заведомо не изоморфны. К простейшим инвариантам относятся: число вершин, число ребер, степени вершин, последовательность степеней (отсортированный список степеней всех вершин), число компонент связности, наличие циклов определенной длины и так далее. Однако эти инварианты не являются полными: существуют неизоморфные графы с одинаковым числом вершин, ребер и даже одинаковыми последовательностями степеней. Для полного решения задачи изоморфизма в общем случае не известно эффективного (полиномиального) алгоритма, но для многих практических случаев можно справиться с помощью специальных методов. В нашем курсе мы будем использовать изоморфизм в основном для распознавания простых ситуаций, например, на небольших графах.

Почему важно понимать изоморфизм? Потому что при построении моделей реальных систем мы часто отождествляем графы, которые получаются переименованием объектов. Например, топология компьютерной сети не зависит от того, как названы серверы – важна лишь схема соединений. Поэтому два графа, задающих одну и ту же сеть, считаются одинаковыми, то есть изоморфными.

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

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

Первый и самый наглядный – **геометрический** (или рисунок). Но он удобен только для небольших графов и не пригоден для алгоритмической обработки.

Второй способ – **матрица смежности**. Для графа с \( n \) вершинами строится квадратная таблица (матрица) размера \( n \times n \), в которой элемент на пересечении строки \( i \) и столбца \( j \) равен 1, если существует ребро (или дуга) из вершины \( i \) в вершину \( j \), и 0 в противном случае. Для неориентированного графа матрица смежности симметрична относительно главной диагонали. Для взвешенного графа вместо 1 записывают вес ребра, а отсутствие ребра обозначают либо 0, либо специальным символом (например, бесконечностью), чтобы не путать с нулевым весом.

Третий способ – **матрица инцидентности**. Эта матрица имеет размеры \( n \times m \), где \( n \) – число вершин, \( m \) – число ребер. Строки соответствуют вершинам, столбцы – ребрам. Для неориентированного графа в столбце, соответствующем ребру \( \{u, v\} \), ставится 1 в строках \( u \) и \( v \), а в остальных строках 0. Для ориентированного графа обычно ставится 1 в строке начала дуги, -1 в строке конца дуги, а для петель – иногда 0 или другое условное значение. Матрица инцидентности менее удобна для большинства алгоритмов, но полезна в некоторых теоретических задачах.

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

Пятый способ – **список смежности**. Для каждой вершины составляется список всех соседей (для ориентированных – список вершин, в которые ведут дуги из данной вершины). Это, пожалуй, самый часто используемый способ в алгоритмах на графах, потому что он позволяет быстро перебирать соседей и эффективно по памяти.

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

### Примеры из ИТ для неориентированных графов

1. **Топология компьютерной сети (физическая)**. Представьте офис, в котором несколько компьютеров соединены между собой с помощью Ethernet-кабелей (топология «общая шина» или «звезда»). Компьютеры – это вершины графа, а кабели между ними – это рёбра. Поскольку данные по кабелю можно передавать в обе стороны (дуплексный режим), рёбра не имеют направления. Такой граф помогает анализировать, какие узлы могут обмениваться пакетами напрямую, и выявлять точки отказа (например, повреждённый кабель разрывает связь).

2. **Схема соединения процессоров в многопроцессорной системе** (например, топология «гиперкуб» или «тор»). Процессоры – вершины, коммуникационные каналы – рёбра. Это неориентированный граф, так как передача данных возможна в обе стороны. Анализ степени вершин позволяет оценить нагрузку на каждый процессор и количество каналов, необходимых для построения отказоустойчивой системы.

### Примеры из ИТ для ориентированных графов

1. **Ссылочная структура веб-сайта**. Страницы сайта – это вершины, а гиперссылки, ведущие с одной страницы на другую, – это дуги. Ссылка действует только в одном направлении: если страница A ссылается на страницу B, это не означает, что B обязательно ссылается на A. Такой орграф используется поисковыми системами (например, в алгоритме PageRank) для ранжирования страниц: чем больше входящих ссылок с авторитетных страниц, тем выше вес (важность) страницы.

2. **Граф вызовов функций в программе**. В прикладном программном обеспечении или операционной системе функция A может вызывать функцию B. Это направленное отношение. Построив ориентированный граф (где вершины – функции, а дуги – вызовы), можно обнаружить циклические зависимости (например, рекурсию или взаимную рекурсию) и выявить потенциально опасные ситуации вроде бесконечного цикла или переполнения стека.

### Примеры из ИТ для взвешенных графов

1. **Маршрутизация пакетов в компьютерной сети**. Каждое ребро (соединение между двумя маршрутизаторами) имеет вес – например, задержку в миллисекундах, пропускную способность (чем больше пропускная способность, тем меньше вес) или стоимость передачи данных. Алгоритмы маршрутизации (OSPF, EIGRP) строят маршруты с минимальной суммой весов, то есть находят кратчайший путь в взвешенном ориентированном или неориентированном графе. Без весов невозможно выбрать оптимальный путь среди нескольких равных по длине каналов.

2. **Сжатие данных с использованием алгоритма Хаффмана**. Хотя это не совсем классический граф, но построение оптимального префиксного кода основано на взвешенном бинарном дереве (дерево – частный случай графа). Частота появления символа во входном потоке служит весом листовой вершины. Дерево строится так, чтобы наиболее частые символы имели более короткие коды, что уменьшает итоговый размер данных.

### Примеры из ИТ для изоморфизма графов

1. **Поиск одинаковых схем в интегральных схемах (EDA-инструменты)**. При проектировании цифровых микросхем логический вентиль (AND, OR, NOT) и его соединения с другими вентилями образуют граф. Инструменты автоматизации проектирования (например, Synopsis, Cadence) сравнивают фрагменты схем на изоморфизм, чтобы обнаружить повторяющиеся блоки и оптимизировать размещение элементов на кристалле. Если два фрагмента изоморфны (с точностью до переименования вершин), они могут быть заменены одним стандартным библиотечным элементом.

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