Question

Двудольный граф называется полным, если каждая вершина одного множества связана в этом графе ребром с каждой вершиной другого множества, и при этом в графе нет кратных рёбер. Если в первом множестве полного двудольного графа п вершин, а во втором — т вершин, то такой граф обозначается Кn.m.
а)  Изобразите граф K2,3.
б)  Изобразите граф К4,4.

Answer 1

Дано:

1. Граф K2,3: 2 вершины в первом множестве, 3 вершины во втором.
2. Граф K4,4: 4 вершины в первом множестве, 4 вершины во втором.

Найти:

1. Изображение графа K2,3.
2. Изображение графа K4,4.

Решение:

а) Для графа K2,3:

- Обозначим вершины первого множества как A1 и A2.
- Обозначим вершины второго множества как B1, B2 и B3.
- Рёбра: A1 соединяется с B1, B2, B3; A2 соединяется с B1, B2, B3.

Граф будет выглядеть так:

```
A1 -- B1
A1 -- B2
A1 -- B3
A2 -- B1
A2 -- B2
A2 -- B3
```

б) Для графа K4,4:

- Обозначим вершины первого множества как A1, A2, A3, A4.
- Обозначим вершины второго множества как B1, B2, B3, B4.
- Рёбра: каждая вершина A соединяется с каждой вершиной B.

Граф будет выглядеть так:

```
A1 -- B1
A1 -- B2
A1 -- B3
A1 -- B4
A2 -- B1
A2 -- B2
A2 -- B3
A2 -- B4
A3 -- B1
A3 -- B2
A3 -- B3
A3 -- B4
A4 -- B1
A4 -- B2
A4 -- B3
A4 -- B4
```

Ответ:
Граф K2,3 и граф K4,4 изображены выше.