Алгебра логики

[Nastya*****]

Установите соответствие между графами, изображающими буквы русского алфавита, и их названиями.
варианты. квазиэйлеровый, эйлеров, дерево.
буквы. В Е Ж О Ф Б


Решение.
В-квазиэйлеровый
Е-квазиэйлеровый
Ж- дерево
О-эйлеровый
Ф- эйлероввй
Б--квазиэйлеровыЙ

@темы: Теория графов, Дискретная математика

Comments

[Дилетант]

дайте определения дерева, эйлерова и квазиэйлерова графов. По крайней мере, в одном месте ошибка есть.

[Nastya*****]

Ошибка только в одном месте?

[Nastya*****]

Неориентированным деревом называется связный и ациклический неориентированный граф.
Ориентированным деревом называется бесконтурный орграф, у которого полустепень захода у каждой вершины не более 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которого равна 0.

Может Е - дерево?

[Дилетант]

Ошибка только в одном месте?

"Только" и "по крайней мере" разные вещи)
Пока я не узнаю, что такое квазиэйлеров граф, точнее не скажу.

Может Е - дерево?

А почему вы сомневаетесь? Что смущает?

[Nastya*****]

не смущает. Е - ДЕРЕВО.

[Nastya*****]

Ж - дерево. тогда.?

[Nastya*****]

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

[Дилетант]

Ж - дерево. тогда.?

Почему вы спрашиваете? ))

Проверьте В.
И с буквой Ф проблемы. У нее есть вершины вне окружности - на концах перекладины?

[Nastya*****]

В-квазиэйлеровый
Е-дерево
Ж- дерево
О-квазиэйлеровый
Ф- дерево
Б--квазиэйлеровыЙ

[Дилетант]

С деревьями разобрались

В-квазиэйлеровый
О-квазиэйлеровый
Ф- дерево
Б--квазиэйлеровыЙ

Почему?
Я не говорю, что всё неправильно (неправильно только кое-что). Просто обоснуйте. Заодно, может быть, сами ошибки найдёте.

[Дилетант]

"О" можете нарисовать, не отрывая карандаш от бумаги и вернуться, откуда начали?
Какие из указанных букв можно так нарисовать?

[Nastya*****]

В-эйлеровый (потому что проходит через вершины? не дерево точно и вряд ли квазиэйлеровый)
О-квазиэйлеровый (потому что можно нарисовать не открывая карандаша от бумаги)
Ф- эйлеров (проходит через все вершины)
Б--квазиэйлеровый (потому что можно нарисовать не открывая карандаша от бумаги)

[Дилетант]

В-эйлеровый

Да. Но объяснение плохое. Можно пройти по всем ребрам по одному разу и при этом вернуться в ту же вершину? Если да, граф эйлеров.
Или граф эйлеров тогда и только тогда, когда он связный и в нём отсутствуют вершины нечётной степени. Проверьте так. У В три вершины: у двух степени 2 и у одной степень 4.

О-квазиэйлеровый (потому что можно нарисовать не открывая карандаша от бумаги)

проверьте по определению. Да, можно нарисовать. Но условие эйлеровости сильнее, чем квазиэйлеровость. Является ли этот граф эйлеровым?

Ф- эйлеров (проходит через все вершины)

Нет. "проходит через все вершины" этого мало. Прочтите определение (хотя бы моё выше).

Б--квазиэйлеровый

да

[Nastya*****]

О - может быть эйлеровым. потому что проходит через все вершины.

[Nastya*****]

Ф - квазиэйлеровый?

[Дилетант]

О - может быть эйлеровым. потому что проходит через все вершины.

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

[Дилетант]

Ф - квазиэйлеровый?

да

[Nastya*****]

спасибо.