Задание 4. Виды графов

Вариант 1

Нарисовать основание следующего графа:

Вариант 2

Нарисовать псевдограф с пятью вершинами.

Вариант 3

Нарисовать мультиграф, мультичисло которого равно трем. Привести примеры кратных ребер.

Вариант 4

Нарисовать граф, не являющийся простым. Объяснить, почему данный граф не простой.

Вариант 5

Нарисовать граф К₆. Привести примеры инцидентных и неинцидентных вершин и ребер.

Вариант 6

Нарисовать два различных подграфа следующего графа:

Вариант 7

Нарисовать граф К_2,4. Привести примеры смежных вершин и ребер и несмежных вершин и ребер.

Вариант 8

Нарисовать граф С₇.

Вариант 9

Нарисовать дополнение следующего графа:

Вариант 10

Нарисовать регулярный, но не полный граф степени 4.

Вариант 11

Нарисовать орграф с одним источником и двумя стоками. Указать, какие вершины являются источниками, какие – стоками.

Вариант 12

Нарисовать граф, имеющий четыре компоненты связности.

Вариант 13

Нарисовать граф, в котором нет мостов, но есть точка сочленения. Указать, какая из вершин является точкой сочленения.

Вариант 14

Нарисовать связный орграф с шестью вершинами, не являющийся сильно связным. Доказать что данный граф не связан сильно.

Вариант 15

Перечислить (списками вершин) сильно связные компоненты следующего графа. Нарисовать конденсацию данного графа.

Вариант 16

Нарисовать граф, не являющийся планарным. Доказать, что данный граф не может быть планарным.

Вариант 17

Нарисовать лес, состоящий из трех деревьев. Перечислить вершины, образующие каждое дерево.

Вариант 18

Нарисовать все различные свободные деревья с пятью вершинами.

Вариант 19

Нарисовать ордерево высоты 4, у которого расстояние между узлами a и b равно шести.

Вариант 20

Нарисовать бинарное дерево с восемью вершинами. Перечислить листья данного дерева.