2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Задача со связным графом
Сообщение13.07.2015, 14:29 
Аватара пользователя


14/09/12
181
Уфа
Цитата:
В связном графе отметили $2n$ вершин. Докажите, что их можно разбить на пары и соединить непересекающимися по ребрам путями.

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача со связным графом
Сообщение13.07.2015, 16:14 


29/06/15
270
[0,\infty )
netang в сообщении #1036612 писал(а):
Выделим из исходного графа связный граф, такой, что из одной вершины исходит только два ребра. Кстати, как такой граф называется?
Тогда исходный граф называется гамильтонов, а то, что выделено -гамильтонов цикл. Но не всякий связный граф - гамильтонов, например крест (вершины -это 4 конца креста и его центр). Поэтому доказательство простое, но для частного случая.

 Профиль  
                  
 
 Re: Задача со связным графом
Сообщение14.07.2015, 15:08 
Аватара пользователя


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

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

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


12/08/10
1017
Тут работает метод крайнего.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group