Частичные графы. подграфы. частичные подграфы.

Граф H(x) называется частичным для графа G(X), если все ребра H(X) являются ребрами G(X) и множество вершин графа H(X) совпадает с множеством вершин графа G(X), то есть H(x) I G(x)x I X, как показано на рисунке 7.

Частичный граф содержит часть ребер (дуг). Он также может быть ориентированным или неориентированным в зависимости от исходного.

Отметим, что ноль-граф графа G(X) считается частичным графом каждого графа. Все частичные графы H(X) для G(X) можно получить, выбирая в качестве ребер H(X) всевозможные подмножества множества ребер графа G(X).

Подграфом GA(A) графа G(X), где A I X, называется граф, вершинами которого являются элементы множества A I X, а ребрами – все ребра из G, оба конца которых лежат в A, как показано на рисунке 8.

Таким образом, подграф содержит часть вершин вместе с ребрами, соединяющими эти вершины. Подграф будет ориентированным или неориентированным в зависимости от графа.

Частичным подграфом HA(A), A I X графа G(X) называется подграф (рисунок 9), ребрами которого являются некоторые ребра из G(X), оба конца которых лежат в A.

Дополнительным частичным графом H(A) графа G(X) является единственный граф, состоящий из ребер графа G(X), не принадлежащих некоторому частичному подграфу HA(A) графа G(X) (рисунок 10).

Звездным графом, определяемым вершиной х, называется граф, состоящий из всех ребер G(X), имеющих х концевой вершиной. Петли в х могут как включаться, так и не включаться в звездный граф.

Дерево и лес.

На практике широко используются такие виды графов, как деревья и прадеревья.

Деревом называется конечный связный неориентированный граф, состоящий по крайней мере из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер (Рисунок 11.).

Ветвямидерева называются ребра графа, входящие в дерево. Хордами дереваназываются ребра, входящие в граф, дополнительный к данному дереву.

Лагранжевым деревом называется дерево, все ветви которого имеют общую вершину.

Лесом называется несвязный граф без циклов, каждая компонента связности которого является деревом.

Прадеревом называется орграф G(X) с корнем x1 I X, если в каждую вершину xi ¹ x1 (xi I X) заходит ровно одна дуга, в вершину x1 не заходит ни одна дуга, граф G(Х) не содержит контуров (рисунок 12).

Вопросы для активизации и создания проблемной ситуации.

1. Что представляет собой граф? В каких областях встречаются графы?

2. Как можно задать граф? Что называют вершинами и ребрами графа?

3. Какие ребра в графе называют ориентированными, какие неориентированными? Что такое дуга?

4. Определите различия между ориентированным, неориентированным и смешанным графом. Как составить обратный граф?

5. Дайте определения полного ориентированного и неориентированного графов.

6. Дайте определение мультиграфа.

7. Дайте понятие цепи неориентированного графа.

8. Какая цепь называется простой, какая составной?

9. Дайте определение пути ориентированного графа.

10. Какие пути являются простыми, сложными, элементарными?

11. Что такое контур графа? Какими бывают контуры?

12. Дайте понятие связности в графах.

13. Дайте определение дерева.

14. Дайте понятие леса.

15. Дайте понятие прадерева.

Раздел 3. Основные понятия архитектуры ЭВМ

Лекция №5. Обзор и история архитектуры компьютера (1 час)

Цель лекции: Изучить историю развития компьютеров; проанализировать развитие компьютеров по поколениям; дать понятие архитектуры компьютера и их классификации; определить принципы определяющие архитектуру компьютера; провести обзор архитектуры компьютера; понятие открытой и закрытой архитектуры.

Вопросы лекции:

1. История развития компьютеров

2. Архитектура и классификация компьютеров

3. Принципы, определяющие архитектуру компьютера

4. Обзор архитектуры компьютеров

Содержание лекции:

Статьи к прочтению:

Лекция 11: Теория графов. Основные понятия

Похожие статьи: