Question

Постройте граф, вершины которого соответствуют восьми подмножествам трёхэлементного множества {а, b, с] и две вершины связаны ребром, только если:
а)  одно из соответствующих подмножеств содержит другое;
б)  в соответствующих подмножествах количество элементов отличается не больше, чем на единицу.

Answer 1

Дано:

Трехэлементное множество {a, b, c}. Подмножества этого множества: {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.

Найти:

Граф, вершины которого соответствуют восьми подмножествам, с рёбрами по заданным условиям.

Решение:

Подмножества:
1. P1 = {}
2. P2 = {a}
3. P3 = {b}
4. P4 = {c}
5. P5 = {a, b}
6. P6 = {a, c}
7. P7 = {b, c}
8. P8 = {a, b, c}

Теперь определим рёбра по условиям:

а) Вершины связаны, если одно подмножество содержит другое:
- P1 связано с P2, P3, P4, P5, P6, P7, P8
- P2 связано с P5, P6, P8
- P3 связано с P5, P7, P8
- P4 связано с P6, P7, P8
- P5 связано с P8
- P6 связано с P8
- P7 связано с P8

б) Вершины связаны, если количество элементов отличается не больше чем на единицу:
- P1 связано с P2, P3, P4
- P2 связано с P1, P5, P8
- P3 связано с P1, P5, P7, P8
- P4 связано с P1, P6, P8
- P5 связано с P2, P3, P8
- P6 связано с P4, P8
- P7 связано с P3, P8
- P8 связано с P2, P3, P4, P5, P6, P7

Теперь объединим условия:

Рёбра:
- P1 - P2, P3, P4, P5, P6, P7, P8
- P2 - P5, P6, P8
- P3 - P5, P7, P8
- P4 - P6, P8
- P5 - P8
- P6 - P8
- P7 - P8

Ответ:

Граф имеет 8 вершин с рёбрами, установленными по указанным условиям.