2014 dxdy logo

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

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




 
 Граф, полученный из K_{42} удалением n ребер - эйлеров
Сообщение14.01.2009, 12:02 
доказать, что граф, полученный из полоного графа $K_{42} удалением $n$ ребер, не имеющих общих вершин, является эйлеровым графом.... где можно посмотреть доказательство, что граф является эйлеровым....а то в учебнике как то не совсем понятно! :(

 
 
 
 
Сообщение14.01.2009, 12:09 
Аватара пользователя
для того чтобы связный граф был эйлеровым необходимо и достаточно, чтобы степени всехвершин были чётными. Эйлеров граф можно обойти "не отрывая карандаш от бумаги" с возвращением в ту же точку

 
 
 
 
Сообщение14.01.2009, 12:10 
"граф является эйлеровым тогда и только тогда, когда он связен и все его локальные степени четны."
если исходить из этого определения. то получается, что нужно доказать связность графа и четность степеней?

 
 
 
 
Сообщение14.01.2009, 12:12 
Аватара пользователя
Пардон, про связность забыл сказать, но Вы правильно всё написали

 
 
 
 
Сообщение14.01.2009, 12:13 
хм....а как четность доказывается? я тут нашла в интернете...но там пропущена половина решения подоной задачи...где можно глянуть, чтоб подробно было?

 
 
 
 
Сообщение14.01.2009, 12:30 
Аватара пользователя
Какова степень вершин графа $K_{42}$?
Вы удаляете из него 21 ребро. При этом они не пересекаются по вершинам. Сколько вершин будет задействовано? На сколько уменьшится степеь каждой вершины?
Помните, что Ваш номер варианта - 21! И n у Вас равно 21!

Добавлено спустя 6 минут 52 секунды:

Связность не забудьте доказать. Для любых двух вершин добавим любую третью и докажем, что из трех ребер треугольника мы можем удалить только одно.

 
 
 
 
Сообщение14.01.2009, 12:42 
благодарю=)

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


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