3 задачи по дискретной математике

citromon · Сообщение **citromon** » 02 июн 2012, 19:12

Доброго времени суток .

Вот не могу справиться с 3 задачами по ДМ.

1. Даны 2 булевы функции:
$(x\downarrow y)\mapsto (z\downarrow y)$
$(x | y)\mapsto (z | y)$ .

Как определить их совершенные и нормальные формы, фиктивные и существенные координаты?

2. Две вершины графа имеют степени 5 и 7, все остальные вершины имеют степень 12.
Доказать, что существует цепь, соединяющая вершины со степенями 5,7.

Код: Выбрать все

По идее, тут нужн оприменить лемму о рукопожатиях.

3. В графе не больше $\frac {n-1} {2}$ вершин, где n - число рёбер. Доказать, что граф связен.

Подскажите, пожалуйста, как их решить.

СергейП

2. А если не существует цепи, соединяющей вершины со степенями 5, 7, то это что значит?

3. А это неверно, скорее всего, неправильно переписаны условия

citromon · Сообщение **citromon** » 02 июн 2012, 20:59

СергейП, я так предполагаю:

Двум вершинам графа с степенями 5 и 7 дадим имена u и v.

Поскольку u и v имеют нечётную степень, а все остальные вершины - четную, то исходя из леммы о рукопожатиях (сумма всех вершин графа - четная) следует, что либо граф связный, либо u,v содержатся в связном подграфе графа, а следовательно существует цепь соединяющая вершины u и v, т.к. в связном графе можно провести цепь из любой его вершины в любую другую.

СергейП

citromon писал(а):Source of the post СергейП, я так предполагаю:

Двум вершинам графа с степенями 5 и 7 дадим имена u и v.

Поскольку u и v имеют нечётную степень, а все остальные вершины - четную, то исходя из леммы о рукопожатиях (сумма всех вершин графа - четная) следует, что либо граф связный, либо u,v содержатся в связном подграфе графа, а следовательно существует цепь соединяющая вершины u и v, т.к. в связном графе можно провести цепь из любой его вершины в любую другую.

Доказательство какое-то не очень чёткое.

Лучше было просто ответить на вопрос, тогда можно доказать так:

Пусть в графе нет цепи, связывающей вершины со степенями 5 и 7, тогда эти вершины принадлежат к разным компонентам связности графа, но сумма степеней вершин в этих компонентах будет нечётной, что невозможно. Следовательно, искомая цепь существует.

citromon · Сообщение **citromon** » 03 июн 2012, 10:39

Спасибо, СергейП.

А почему вы думаете, что вторая задача переписана неверно?

СергейП

citromon писал(а):Source of the post А почему вы думаете, что вторая задача переписана неверно?

Речь о 3-ей?

Несложно контрпример построить.

citromon · Сообщение **citromon** » 03 июн 2012, 11:24

Да, я её имел в виду.

yourdomain.com