АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Граф G1 = (V1,U1) называется подграфом графа G2 = (V2, U2), если V1 V2 и U

Прочитайте:
  1. I. Доход от прироста стоимости при реализации ценных бумаг (инвестор самостоятельно несет ответственность за определение и выплату налогов в бюджет Республики Казахстан)
  2. I. ОПРЕДЕЛЕНИЕ ОСНОВНЫХ ТЕРМИНОВ
  3. I. Определение СКФ по клиренсу креатинина
  4. II. Договорные отношения могущие влиять на определение управомоченного лица
  5. А. Определение группы крови стандартными изогемагглютинирующими сыворотками.
  6. Аборты. Определение, классифиация, диагностика и профилактика.
  7. Ангины: 1) определение, этиология и патогенез 2) классификация 3) патологическая анатомия и дифференциальная диагностика различных форм 4) местные осложнения 5) общие осложнения
  8. Антигены. Определение. Свойства. Виды.
  9. Асептика, антисептика. Определение понятий. Способы проведения.
  10. Б. Определение группы крови с помощью цоликлонов (моноклональных антител)

Граф 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 | Просмотры: 477 | Нарушение авторских прав

При использовании материала ссылка на сайт medlec.org обязательна! (0.002 сек.)