Найти все графы, в которых каждая пара рёбер имеет общий конец. Обосновать почему найдены все (не все)

задан 22 Окт '19 21:12

10|600 символов нужно символов осталось
0

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

Рассмотрим произвольное ребро AB. Любое другое ребро имеет в качестве концевой вершины A или B. Предположим, что есть другие рёбра как с концом A, так и с концом B. Тогда у них есть общая вершина C. При этом получается граф треугольника. Понятно, что других рёбер быть уже не может (если есть AD, то оно не имеет общих вершин с BC.

Остался случай, когда из A или B больше рёбер не исходят. Можно принять второе. Тогда все рёбра исходят из A. Это даёт так называемый звёздный граф. Число рёбер в нём может быть любое. Он удовлетворяет условию.

Итого имеем звёздный граф или треугольник (плюс отдельные изолированные вершины, если они есть).

ссылка

отвечен 22 Окт '19 22:10

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×640

задан
22 Окт '19 21:12

показан
882 раза

обновлен
22 Окт '19 22:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru