ГДЗ по вероятность и статистика 7-9 класс Высоцкий, номер 125

№

Неодинаковые графы с одинаковыми степенями

Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.

Решение

Обозначим вершины A, B, C, D, E, F. В первом графе проведём рёбра AB, AC, AE, BD, BF, CD.

У A рёбра AB, AC, AE, поэтому степень ; у B — BA, BD, BF, тоже . У C есть CA, CD, у D — DB, DC, значит, степени равны . У E и F по одному ребру. Все вершины соединены через путь E–A–B–F и ветвь A–C–D–B.

Во втором графе проведём AB, AC, AD, BC, BD и EF.

У A и B опять степени , у C и D — , у E и F — . Но ребро EF отделено от остальных: второй граф состоит из двух отдельных частей. Первый граф такой отдельной части не имеет. Значит, никаким передвижением вершин нельзя получить второй граф из первого; они неодинаковы.

Ответ

Первый граф: AB, AC, AE, BD, BF, CD; второй: AB, AC, AD, BC, BD, EF. Оба имеют заданные степени, но второй граф распадается на две части.

Помогло?

Номер 125