Втягивание вершины: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Втягивание вершины''' (''Vertex involving'') - преобразование орграфа, состоящее в о...) |
KVN (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
'''Втягивание вершины''' (''Vertex involving'') | '''Втягивание вершины''' (''[[Vertex involving]]'') — преобразование [[орграф|орграфа]], состоящее в [[отождествление вершин|отождествлении вершин]] <math>a</math> и <math>b</math>, связанных дугой <math>(a,b)</math>, причем эта [[дуга]] — единственная [[заходящая дуга|заходящая]] в <math>b</math> дуга. | ||
преобразование орграфа, состоящее в отождествлении вершин <math>a</math> и | |||
<math>b</math>, связанных дугой <math>(a,b)</math>, причем эта дуга | |||
заходящая в <math>b</math> дуга. | |||
[[Файл:Vertex involving.png|350px]] | |||
Другое название — ''[[Слияние двух вершин]]''. | |||
См. также ''Разборный граф''. | |||
==См. также== | |||
* ''[[Разборный граф]]''. | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
[ | [[Категория: Сводимые и регуляризуемые графы]] | ||
Текущая версия от 12:08, 4 сентября 2019
Втягивание вершины (Vertex involving) — преобразование орграфа, состоящее в отождествлении вершин [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math], связанных дугой [math]\displaystyle{ (a,b) }[/math], причем эта дуга — единственная заходящая в [math]\displaystyle{ b }[/math] дуга.
Другое название — Слияние двух вершин.
См. также
Литература
- Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.