Графы. Самостоятельная работа.

Самостоятельная работа

Графы

Фамилия, имя

Алашкин Александр

Вариант

2

Воронин Максим

Фамилия, имя

3

Григорьев Антон

Журавлев Данила

Вариант

Суворов Даниил

4

14

Ильин Михаил

5

Холопов Александр

6

Кодиров Муроджон

Плигин Николай

15

7

Лебедев Владислав

16

Чекмарев Вадим

Чумичев Александр

17

Манузин Алексей

8

Маслов Алексей

9

Стойка Дмитрий

18

Козулина Юлия

19

10

Смахтин Никита

11

Лазарев Дмитрий

20

Фалилеев Алексей

12

Якфуфи Васим

21

Показаченко Андрей

22

Перепелица Владислав

13

23

24

25

1. Изобразить неориентированный граф, состоящий из

ВАРИАНТ

ВЕРШИН

1

РЕБЕР

5

8

Вариант 1

Вариант 2

2. Выписать две пары смежных и не смежных вершин

1 и 2, 1 и 4

Смежные вершины:

1 и 2, 1 и 3

НЕ смежные вершины:

{1,4}, {3,6}

{1,4}, {5,2}

3.Выписать две пары смежных и не смежных вершин

Смежные ребра:

{1,2}, {1,3}

{1,2}, {1,4}

Два ребра инцидентные одной вершине называются смежными.

Две вершины инциденты одному ребру называются смежными.

{1,2}, {3,4}

{1,2}, {4,5}

НЕ смежные ребра:

4. Выписать ребра, инцидентные вершине № 3.

{3,1}, {3,2}, {3,4}, {3,5}

{3,2}, {3,4}, {3,5}

5. Построить петлю в вершине №2.

6. Достроить на графе изолированную вершину.

Общее понятие связности распространяется только на неориентированные графы. Для описания ориентированных графов используются понятия сильной и слабой связности.

7. Указать степени всех вершин.

Смежные ребра:

Смежные ребра:

{1,2}, {1,4}

8. Изобразить любой подграф

Компоненты связности

2

4

1

5

6

7

3 компонента связности

1 компонент связности

2 компонента связности

Компонента связности – набор вершин графа, между любой парой которых существует путь

9.Указать компоненты связанности данного графа.

Компонент связанности = 2

Компонент связанности = 2

10. Изобразить неориентированный, связанный граф по заданным условиям.

ВАРИАНТ

1

КОЛ-ВО ВЕРШИН

6

СТЕПЕНЬ

СТЕПЕНЬ

3(9)

5(5)

СТЕПЕНЬ

1(4)

11. Описать данный граф

• Вид графа: неориентированный псевдограф,

• Кратные (параллельные) ребра: {(1,3) 3 , (5,3) 3 } Изолированная вершина:
• Кратные (параллельные) ребра: {(1,3) 3 , (5,3) 3 }
• Изолированная вершина:

• Петля к вершине
• Петля к вершине

Псевдограф ( петли и (или) параллельные ребра)

Мультиграф (параллельные ребра)

12 . Изобразить ориентированный не связанный граф, состоящий из

ВАРИАНТ

ВЕРШИН

1

РЕБЕР

6

8

13.Указать степени исходящих дуг.

14 Выписать все пути из точки 2 в точку 5 и найти их длину (если пути не существует, то выбрать любой произвольный путь и найти его длину)

Путь:

Длина:

2

3

Длина пути - количество входящих в этот путь ребер

Путь - маршрут без повторяющихся дуг

Ребро (А,В) называется мостом графа

• Если в графе, полученном после удаления из графа ребра (А,В), вершины А и В оказываются несвязанными.

Примеры

Мост

4

В

А

3

6

2

5

E

F

7

С

8

1

D

Любое ребро – мост

Выделите на графе ребра, которые являются мостами

1)

2)

4

4

6

3

5

5

2

3

2

7

6

8

7

1

1

8

Ответ

15. Дорисовать мост

Мост

Точка сочленения графа G

— вершина, при удалении которой в графе увеличивается число компонент связности

ребро с таким же свойством называется мостом

Точка сочленения

7

2

a

6

4

1

3

8

мост

9

10

5

При удалении вершины 6:

стало 3 компонента связности

Точка сочленения графа G

— вершина, при удалении которой в графе увеличивается число компонент связности

a1

a2

a3

точки сочленения графа G

16. Выделить точку сочленения

Точка сочленения

11. Описать данный граф.

12 . Изобразить ориентированный не связанный граф, состоящий из