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

Пусть задан граф G =(V, E).

Подграф G – граф G ₁=(V ₁, E ₁): V ₁Í V, V ₁¹Æ, E ₁Í E. Обозначается этот факт: G ₁Í G. (G ₁ называют также частью G.)

Пусть V ₁Í V, V ₁¹Æ. Подграфом G, порожденным множеством V ₁, называется граф G ₁=(V ₁, E ₁): E ₁ состоит из тех и только тех элементов E, начала и концы которых лежат в E ₁.

Теорема. Пусть G =(V, E) – некоторый граф, а G ₁=(V ₁, E ₁), V ₁Í V, V ₁¹Æ – подграф G, порожденный множеством V ₁. Тогда – подматрица матрицы A_G, находящаяся на пересечении строк и столбцов, соответствующих вершинам из V ₁.

Дата добавления: 2014-01-04