Идеальное совпадение в дереве

Question

Я наткнулся на определение идеального соответствия: набор ребер, который касается каждого узла ровно один раз.

Однако я не совсем понял определение.Может ли кто-нибудь дать мне пример любого такого преимущества.Или, может быть, указывают мне на какую-то ссылку, которая делает.

Я пытался гуглить, но это не дало мне никакого примера.

Answer 1

Идеальным подходящим набором является любой набор ребер в графе, где каждая вершина графа касается ровно одного ребра в соответствующем наборе.Если вы рассматриваете граф с четырьмя связанными вершинами, так что граф напоминает квадрат, есть два идеально подходящих набора, которые являются парами параллельных ребер.Поскольку все вершины касаются ровно один раз любой парой.Если вы думаете о графе с 3-мя вершинами, соединенными как треугольник, не существует идеального совпадающего множества, потому что если вы берете любую пару ребер, то к одной вершине прикасаются дважды, но одно ребро всегда пропускает вершину.1002 *http://en.wikipedia.org/wiki/Perfect_matching

В вашем вопросе упоминается дерево, но дерево - это просто особый тип графика, поэтому он все еще работает так же.

Answer 2

На самом деле, любой граф с нечетным числом вершин не может иметь идеально подходящее множество ребер.

N ребер => 2 * N вершин.Так как ни одна вершина, которой когда-либо касались, больше не должна касаться.