Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных. - презентация

1 Теория графов Основные определения

2 Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных ребрами – ребро d между вершинами А и В, ребро e между вершинами В и С, ребро f между вершинами В и А, ребро g между вершиной С и С. – Как называется ребро е по отношению к ребру d? – Как называется ребро g?

3 Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа

4 Задание графов По матрице смежности построить граф abcd a0110 b1010 c1101 d0010

5 Задание графов Построить граф, если задана матрица инцидентности uvwx a1000 b1110 c0101 d001 1

6 Изоморфизм Показать, что следующие два графа изоморфны

7 Изоморфизм Изобразить все попарно неизоморфные 4- вершинные графы без петель и кратных ребер. Изобразить все попарно неизоморфные несвязные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.

8 Изоморфизм и степень вершин Изобразить все попарно неизоморфные 6- вершинные графы без петель и кратных ребер со следующим набором степеней вершин (2, 2, 3, 3, 3, 5) Изобразить все попарно неизоморфные не имеющие петель и кратных ребер кубические графы с 6 вершинами (кубические – однородные (у которых все вершины – одинаковой степени) графы со степенью 3)

9 Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.

10 Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.

11 Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.