2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача со связным графом
Сообщение13.07.2015, 14:29 
Аватара пользователя
Цитата:
В связном графе отметили $2n$ вершин. Докажите, что их можно разбить на пары и соединить непересекающимися по ребрам путями.

Выделим из исходного графа связный граф, такой, что из одной вершины исходит только два ребра. Кстати, как такой граф называется? После чего пронумеруем вершины. Возьмём минимальный номер вершины, который соответствует одной из отмеченных $2n$ вершин. Начиная с него и до максимального номера вершины, который соответствует одной из отмеченных $2n$ вершин, выделим $n$ пар непересекающихся между собой по ребрам вершин. Так можно доказать?

(Оффтоп)

Тема с такой задачей уже была [http://dxdy.ru/topic58224.html], но я не хотел подсматривать.

 
 
 
 Re: Задача со связным графом
Сообщение13.07.2015, 16:14 
Аватара пользователя
netang в сообщении #1036612 писал(а):
Выделим из исходного графа связный граф, такой, что из одной вершины исходит только два ребра. Кстати, как такой граф называется?
Тогда исходный граф называется гамильтонов, а то, что выделено -гамильтонов цикл. Но не всякий связный граф - гамильтонов, например крест (вершины -это 4 конца креста и его центр). Поэтому доказательство простое, но для частного случая.

 
 
 
 Re: Задача со связным графом
Сообщение14.07.2015, 15:08 
Аватара пользователя
Спасибо, что ответили!
Попытка номер 2.
Изображение
1. Связный граф всегда можно "расчесать", и получить граф в виде дерева (рис. 1).
2. Если на концах такого дерева имеются отмеченные точки, то возникает два варианта:
    1. Таких точек чётное количество на одной макушке.
    2. Таких точек нечётное количество на одной макушке.
Если таких точек чётное количество, то образуем пары из этих вершин и удалим эти вершины из графа.
Если таких точек нечётное количество, то после образования пар из вершин на этой макушке и последующего удаления, останется одна отмеченная вершина. При этом, если на конце ветки осталась одна отмеченная вершина и она соединена с неотмеченной вершиной, которая "свободна-болтающаяся", то её удаляем из графа. (рис. 2)
Все макушки с неотмеченными вершинами тоже удаляем.
Таким образом, повторяя действия описанные выше, мы можем разбить отмеченные пары таким образом, что они не будут пересекаться по ребрам путями.

Извините за косноязычность. С теорией графов почти не знаком.

 
 
 
 Re: Задача со связным графом
Сообщение15.07.2015, 12:01 
Тут работает метод крайнего.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group