1.
Нарисуйте граф, вершинами которого являются натуральные числа от 1 до 15, а рёбрами соединены числа, одно из которых делится на другое
2.
Постройте граф с пятью вершинами, в котором нет ни трёх попарно соединённых, ни трёх попарно несоединённых вершин.
3.
Нарисуйте все неизоморфные друг другу графы с четырьмя вершинами.
- Создаем вершины графа, представляющие натуральные числа от 1 до 15.
- Проверяем все возможные комбинации пар чисел от 1 до 15.
- Если одно из чисел делится на другое без остатка, то соединяем соответствующие вершины ребром.
- Повторяем процесс для всех пар чисел.
- Получаем граф, где вершины представляют числа, а ребра соединяют числа, одно из которых делится на другое.
2. Для построения графа с пятью вершинами, где нет ни трех попарно соединенных, ни трех попарно несоединенных вершин, можно использовать следующий алгоритм:
- Создаем пять вершин графа, обозначаем их буквами A, B, C, D и E.
- Соединяем вершины так, чтобы ни у трех попарно соединенных вершин, ни у трех попарно несоединенных вершин не было.
- Примерно так выглядит граф, удовлетворяющий условию:
A---B
\ /
C
/ \
D---E
3. Для нахождения всех неизоморфных друг другу графов с четырьмя вершинами можно использовать переборный подход:
- Существует всего 11 неизоморфных графов с четырьмя вершинами.
- Можно перебирать графы поочередно и проверять их на изоморфизм, используя различные критерии, как например, количество ребер, степени вершин и т.д.
- Примерно так выглядят все неизоморфные друг другу графы с четырьмя вершинами:
1. O---O 2. O 3. O---O 4. O---O 5. O---O 6. O
| | \ / \ / \ / \
O O---O O O O O
7. O 8. O 9. O---O 10. O---O 11. O---O
| \ / / \ / \ / \
O---O O---O O---O O---O