![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Доказательство
1) Покажем, что если Доказательство будем проводить методом от противного. Пусть существуют две простые цепи, соединяющие вершину u и v. Тогда вершины u и v входят в простой цикл, что противоречит тому, что
u
2) Пусть любые две вершины в Доказательство будем проводить методом от противного. Пусть ребро х – не мост, то есть удаление этого ребра граф остается связным. Тогда в 3) Пусть Древовидность графа будем доказывать методом математической индукции по р. База индукции: р=1, в этом случае q=0. Шаг индукции: пусть
4) Пусть Доказательство будем проводить методом от противного. Пусть есть цикл с n вершинами и n ребрами. Остается (р-n) вершин, которые для того чтобы граф был связным, должны быть соединены не менее, чем (р-n) ребрами ((р-n-1) между собой и одно с циклом). Тогда в графе число ребер 5) Пусть Граф
|