Инд работа1(матр смеж и инцид)

Индивидуальная работа №1

Основные понятия теории графов. Способы задания графов. Операции над графами.

Для выполнения и защиты индивидуальной работы №1 необходимо изучить теоретический материал по данной теме.

Перечень вопросов по первой нидивидуальной работе:

1. Определение графа.

2. Виды графов (н-граф, орграф, псевдограф, мультиграф)

3. Определения ребра, дуги, степени вершины, полустепени исхода и захода вершины, кратности ребер, висячих вершин, петли, понятия смежности и инцидентности.

4. Способы задания графов

5. Матрицы смежности и инцидентности, их свойства.

6. Операции над графами (дополнение графа, пересечение графов, объединение графов, произведение графов)

7. Определение цепи, простой цепи, пути (маршрута), длины пути (маршрута), цикла (контура).

8. Нахождение количества путей длины к в орграфе с помощью матрицы смежности.

9. Выяснение наличия контура в орграфе с помощью матрицы смежности.

№1. Дана реализация графов. Определить к какому типу относятся графы. Задать графы списками вершин и ребер и с помощью матриц смежности и инцидентности. Определить степени всех вершин в графе G, полустепени исхода и полустепени захода всех вершин в орграфе D.

I.

а) б)

G: D:

II.

а) б)

G: D:

III.

а) б)

G:

D:

IV.

а) б)

G: D:

V.

а) б)

G: D:

VI.

а) б)

G: D:

VII.

а) б)

G: D:

VIII. б)

а)

G: D:

IX. б)

а)

G: D:

X.

а) б)

G: D:

№2 Для графа G (см №1) найти два произвольных подграфа G1 и G2 (подграфы должны содержать не менее трех вершин). Составить матрицы смежности и инцидентности графов G1 и G2. Построить графы G1G2, G1G2, G1G2. Найти дополнения графовG1 и G2 до графа G, составить их матрицы инцидентности и смежности.

№3 С помощью матрицы смежности определить количество путей длины 2,3,4 из V1 в V4, из V2 в V5, определить для всех вершин графа полустепени исхода и захода, выяснить имеются ли контуры в графе. Построить реализации графов.

I. II. III. IV.

V. VI. VII. VIII.

IX. X.