Вступление
В связи с разработкой одной классной штуки приходится читать сложные материалы по теории графов на английском. И некоторые штуки слишком быстро вылетают из головы. И для упорядочивания знаний, я попишу коротко о некоторых терминах из теории графов о которых нет инфы в рунете.
Включенное дерево(Inclusion tree) - это маркированное дерево P, которое можно получить из маркированного дерева T путем удаления его узлов, если узел v дерева T удален, то все ребра идущие из него заменяются на ребра из родителя v к его детям.
Вроде бы аналогичным понятием является embedded tree. Применений много не знаю, только вот для запросов в структурированные текстовые базы данных.
Можно почитать:
Alarm!!! Этого поста не должно было быть, я перепутал понятия Tree inclusion problem и Inclusion tree. Хоть понятия и пересекаются, но не совсем о том :) Но не удалять же пост
В связи с разработкой одной классной штуки приходится читать сложные материалы по теории графов на английском. И некоторые штуки слишком быстро вылетают из головы. И для упорядочивания знаний, я попишу коротко о некоторых терминах из теории графов о которых нет инфы в рунете.
Включенное дерево(Inclusion tree) - это маркированное дерево P, которое можно получить из маркированного дерева T путем удаления его узлов, если узел v дерева T удален, то все ребра идущие из него заменяются на ребра из родителя v к его детям.
Красный узел -- узел который удаляем.
Вроде бы аналогичным понятием является embedded tree. Применений много не знаю, только вот для запросов в структурированные текстовые базы данных.
Можно почитать:
- http://www.cs.ucr.edu/~stelo/cpm/cpm03/Valiente.pdf
- http://www.mathnet.ru/links/1140e3926c2d8debfd832352d2bd60df/znsl2144.pdf
- http://link.springer.com/chapter/10.1007%2F3-540-57182-5_13#page-1(хотят бабосы)
- http://www2.imm.dtu.dk/~inge/treeInclusion.pdf
Alarm!!! Этого поста не должно было быть, я перепутал понятия Tree inclusion problem и Inclusion tree. Хоть понятия и пересекаются, но не совсем о том :) Но не удалять же пост
No comments:
Post a Comment