АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология
|
ОПРЕДЕЛЕНИЕ. Граф G1 = (V1,U1) называется подграфом графа G2 = (V2, U2), если V1 V2 и U
Граф G 1 = (V 1, U 1) называется подграфом графа G 2 = (V 2, U 2), если V 1 V 2 и U 1 U 2.
Например, граф G 1, приведенный на рис. 5.8., является подграфом графа G 2.
a G 2 a G 1
B b
C c
d
Рис. 5.8.
Удаление из графа G некоторой вершины v, степень которой равна 2, - это замена удаляемой вершины и двух выходящих из нее ребер на одно ребро, соединяющее отличные от v концы удаленных ребер.
Процесс последовательного удаления из графа G одной или нескольких вершин степени 2 называется стягиванием этого графа. Обратная операция для удаления вершин степени 2 называется разбиением ребер.
Заметим, что операции удаления из графа вершин степени 2 и разбиения ребер сохраняют свойства графов быть планарными или непланарными.
Дата добавления: 2015-09-27 | Просмотры: 523 | Нарушение авторских прав
|