@dc65k

Как решить задачу про графы?

Всем привет, подскажите пожалуйста, как решить следующую задачу?
Существует утверждение "Каждый связный граф имеет одну или несколько вершин степени 2". Ниже представлены 5 графов с 1 или более связанных вершин. Какой из 5 графов является контрпримером описанного утверждения?
601b789a397e1130665807.jpeg
  • Вопрос задан
  • 75 просмотров
Решения вопроса 1
wataru
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
Контрпример - это тот, который опровергает утверждение.
Утверждение - каждый связный граф имеет хотя бы одну вершину степени 2.
Т.е. контрпример - связный граф, который не имеет ни одной вершины степени 2.
Степень вершины - это сколько ребер в нее входит. Можете найти такой граф на картинке?
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@U235U235
Распишите степени каждой вершины и ответ будет очевиден. Тут даже думать не надо.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы