Связность и расстояние
Говорят, что вершины
и
в графе смежны, если существует ребро, соединяющее их. Говорят, что два ребра смежны, если они имеют общую вершину. Простой путь, или для краткости, просто путь, записываемый иногда как
, - это последовательность смежных ребер
, в которой все вершины
различны, исключая, возможно, случай
. В орграфе этот путь называется ориентированным из
в
, в неориентированном графе он называется путем между
и
. Число ребер в пути называется длиной пути. Путь наименьшей длины называется кратчайшим путем. Замкнутый путь называется циклом. Граф, который не содержит циклов, называется ациклическим.
Подграф графа
есть граф, вершины и ребра которого лежат в
. Подграф
, индуцированный подмножеством
множества
вершин графа
, - это подграф, который получается в результате удаления всех вершин из
и всех ребер, инцидентных им.
Неориентированный граф
связен, если существует хотя бы один путь в
между каждой парой вершин
и
. Ориентированный граф
связен, если неориентированный граф, получающийся из
путем удаления ориентации ребер, является связным. Граф, состоящий из единственной изолированной вершины, является (тривиально) связным. Максимальный связный подграф графа
называется связной компонентой или просто компонентой
. Несвязный граф состоит из двух или более компонент. Максимальный сильно связный подграф называется сильно связной компонентой.
Иногда недостаточно знать, что граф связен; нас может интересовать, насколько "сильно связен" связный граф. Например, связный граф может содержать вершину, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения или разделяющей вершиной. Граф, содержащий точку сочленения, называется разделимым. Граф без точек сочленения называется двусвязным или неразделимым. Максимальный двусвязный подграф графа называется двусвязной компонентой или блоком.
Большинство основных вопросов о графах касается связности, путей и расстояний. Нас может интересовать вопрос, является ли граф связным; если он связен, то может оказаться нужным найти кратчайшее расстояние между выделенной парой вершин или определить кратчайший путь между ними. Если граф несвязен, то может потребоваться найти все его компоненты. В нашем курсе строятся алгоритмы для решения этих и других подобных вопросов.
Содержание раздела
