2014 dxdy logo

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

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




 
 Доказать признак связности неорграфа
Сообщение12.10.2014, 21:18 
Доказать, что если степень каждой вершины n-вершинного графа без петель $\ge\frac{n-1}{2}$ то он связен. Вот задача. Я дорылся до того, что в любом связном неорграфе количество ребер $\ge n-1$, где $n$ - количество вершин ($n\ge1$). Я пытался доказать от противного: условие выполняется, но граф несвязный. А это значит, что он состоит из $k$ компонент связности ($k\ge2$). Тогда количество ребер исходного графа $\ge n-k$. Вот тут я и застопорился: не могу связать степени никак. Помогите, пожалуйста.

 
 
 
 Posted automatically
Сообщение12.10.2014, 21:29 
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 
 
 
 Posted automatically
Сообщение12.10.2014, 21:51 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

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


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