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

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

На рис. 2.1 изображены граф и три его подграфа, и, среди которых является основным, а — порожденным.

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

.

Операции над графами

Удаление вершины или ребра, а также переход к подграфу — это операции, с помощью которых можно из имеющегося графа получать другие графы с меньшим числом элементов. Известны также операции, позволяющие, наоборот, получать из имеющихся графов «большие» графы. Такова, например, операция добавления ребра: если вершины и графа не смежны, то можно определить граф, где.

.

Он получается из графа добавлением нового ребра .

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

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

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

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