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

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

 

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

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

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

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

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

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

 

 

 

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

 

Дерево и лес.

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

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

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

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

 

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

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

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

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

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

 

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