дано:
Количество вершин в графе:
а) 3
б) 4
найти:
Все возможные графы с заданным количеством вершин.
решение:
а) Для трех вершин (A, B, C):
1. Граф без рёбер: { }
2. Один рёбер: { (A, B) }, { (A, C) }, { (B, C) }
3. Два рёбра: { (A, B), (A, C) }, { (A, B), (B, C) }, { (A, C), (B, C) }
4. Полный граф: { (A, B), (A, C), (B, C) }
Итого: 8 графов.
б) Для четырех вершин (A, B, C, D):
1. Граф без рёбер: { }
2. Один рёбер: { (A, B) }, { (A, C) }, { (A, D) }, { (B, C) }, { (B, D) }, { (C, D) }
3. Два рёбра: { (A, B), (A, C) }, { (A, B), (A, D) }, { (A, B), (B, C) }, и так далее. Всего 15 комбинаций.
4. Три рёбра: множество комбинаций (например, { (A, B), (A, C), (A, D) }) и так далее. Всего 20 комбинаций.
5. Полный граф: { (A, B), (A, C), (A, D), (B, C), (B, D), (C, D) }
Итого: 16 графов.
ответ:
а) 8 графов; б) 16 графов.