Теорема. В любом неориентированном графе $G=(V,E)$ выполняется
$$\sum _{v\in V}\mathrm{deg}(v)=2|E|.$$
Доказательство (двойной счёт). Рассмотрим все упорядоченные пары $(v,e)$, где $v$ — вершина, а $e\in E$ — ребро, инцидентное $v$. С одной стороны, число таких пар равно сумме степеней вершин, т.е.
$$\#\{(v,e)\}=\sum _{v\in V}\mathrm{deg}(v).$$ С другой стороны, каждое ребро без петель инцидентно ровно двум вершинам и даёт 2 таких пары; петля (если разрешена) инцидентна одной вершине, но считается в степени дважды и тоже даёт 2 пары. Следовательно число пар равно $2|E|$. Сравнивая, получаем требуемое равенство:
$$\sum _{v\in V}\mathrm{deg}(v)=2|E|.$$ □
Практические применения теории графов в информатике (кратко):
- Маршрутизация и сети: алгоритмы кратчайшего пути (Dijkstra, Bellman–Ford), остовные деревья (Kruskal, Prim), поток в сети (Ford–Fulkerson, Edmonds–Karp) для маршрутов, балансировки нагрузки, планирования каналов связи.
- Планирование задач и расписаний: моделирование зависимостей как ориентированный ациклический граф (DAG), топологическая сортировка для порядка выполнения, критический путь для оценки времени выполнения.
- Анализ зависимостей и управление пакетами: графы зависимостей, обнаружение циклов (неразрешимые зависимости), сильные компоненты для модульного анализа.
- Сведение и теория вычислимости / сложности: сведение задач NP (например, 3‑SAT, Clique, Vertex Cover, Independent Set) позволяет переносить алгоритмические и сложностные результаты между задачами; структуры графов используются для моделирования физических и логических ограничений.
Пример редукции из 3‑SAT в Clique.
Пусть дана формула в КНФ с $m$ клаузами $C_1,\dots ,C_m$, каждая клаузa содержит не более трёх литералов. Построим граф $G=(V,E)$ и число $k$ так:
- Для каждого вхождения литерала в клаузу создаём вершину. Обозначим вершины вида $v_{i,a}$ — $a$-й литерал в клаузе $C_i$. Тогда
$$V=\{v_{i,a}\mid 1\le i\le m,a\text{литерал в}{C}_i\}.$$ - Проведём ребро между двумя вершинами $v_{i,a}$ и $v_{j,b}$ тогда и только тогда, когда $i\ne j$ и литералы, соответствующие этим вершинам, не являются противоречивыми (т.е. не одно есть $x$, а другое $\neg x$). Заметим, что вершины одной и той же клаузулы не соединяем.
- Положим целевой размер клики $k=m$.
Утверждение: формула выполнима тогда и только тогда, когда в $G$ есть клика размера $m$.
Доказательство корректности редукции:
- Если формула выполнима, возьмём некоторую удовлетворяющую переменную присвоение. В каждой клаузе $C_i$ выберем один истинный литерал; соответствующие вершины $v_{i,\ast }$ принадлежат разным клаузам и не конфликтуют по значениям, значит между любыми двумя такими вершинами проведено ребро, т.е. они образуют клику из $m$ вершин.
- Обратно, если в $G$ есть клика $K$ размера $m$, то так как внутри каждой клаузулы вершины не соединены, вершины клики должны принадлежать разным клаузам — по одной из каждой клаузулы. По построению клики никакие две выбранные вершины не соответствуют противоположным литералам, значит можно присвоить выбранным литералам значение «истина» (любые остальные переменные можно присвоить произвольно), и это даёт удовлетворяющую оценку для всех $m$ клауз.
Сложность редукции: построение $G$ даётся за полиномиальное время по размеру формулы (число вершин не превосходит суммарного числа литералов, рёбер — квадратично в этом числе), поэтому это корректное полиномиальное сведение.
Так редукция показывает, что Clique NP‑трудна, поскольку 3‑SAT — NP‑полная; в комбинации с тем, что Clique лежит в NP, это доказывает NP‑полноту Clique.
(Конец.)