АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Прочитайте:
  1. B) любые сведения, полученные в ходе производства по делу с соблюдением требований уголовно-процессуального законодательства, имеющие отношение к делу
  2. I. Общие сведения
  3. I. Общие сведения.
  4. I. Основные теоретические положения
  5. II. Краткие анамнестические сведения и катамнез.
  6. LXIX. СВЕДЕНИЯТА
  7. А. Общие сведения о ПТО.
  8. Анатомические сведения
  9. ВАЖНЫЕ СВЕДЕНИЯ О СКИПИДАРЕ
  10. Вопрос 4. Кому без согласия пациента или его законного представителя могут быть переданы сведения, относящиеся к медицинской тайне?

Нахождение цикломатического числа в графе

ЦЕЛЬ РАБОТЫ

12.1.1 Ознакомиться с теоретическими сведениями.

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

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

12.2.1 Методические указания по выполнению практической работы.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

12.3.1 Изучить методические указания к практической работе.

12.3.2 В соответствии с вариантом найдите цикломатическое число в графе.

СОДЕРЖАНИЕ ОТЧЕТА

12.4.1 Цель работы

12.4.2 Методические рекомендации

12.4.3 Порядок выполнения работы

12.4.4 Ответы на контрольные вопросы

12.4.5 Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

12.5.1 Что такое дерево?

12.5.2 Дайте определение цикломатическому числу?

12.5.3 Что такое лист?

12.5.4 Что такое высота дерева?

12.5.5 Что такое ярус?

12.5.6 Что такое лес?

12.5.7 Что такое корень дерева?

12.5.8 Наиболее характерные свойства деревьев?

12.5.9 Что называется ветвью?


ПРИЛОЖЕНИЕ 1

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

 

Дерево — связный неориентированный граф, в котором отсутствует цикл.

Лес — это граф, компоненты которого являются деревьями (почему бы и нет!). Понятие дерева широко используется во многих областях математики и информатики. Например, они используются как инструмент при вычислениях, как удобный способ хранения данных, способ сортировки или поиска данных.

Дерево и названо деревом, поскольку, будучи нарисованным, выглядит как дерево, только перевернутое "вверх ногами". Граф, изображенный на рис. 6.34, является примером дерева.

Граф на рис. 6.35 не является деревом, поскольку содержит цикл. Граф на рис. 6.36 — это лес.

Каждая вершина дерева называется узлом.

 

Достаточно развитое генеалогическое дерево образует дерево. Если начать с конкретной (хорошо известной) личности и провести ребра между каждым из родителей и каждым сыном или дочерью, это сформирует дерево. При построении генеалогического дерева, однако, необходимо быть очень осторожным, чтобы браки между дальними родственниками не образовывали циклов.

Другим примером дерева может служить организационный устав. Дерево на рис. 6.37 — типичное частичное организационное дерево для университета. В этом разделе, тем не менее, деревья будем рассматривать как графы.

 

 

Предположим, что дерево представляет собой физический объект, подвижный в вершинах, и подвесим дерево за одну из его вершин так, что остальная его часть повиснет ниже этой вершины. Например, пусть задано дерево на рис. 6.39.

Если подвесить его за вершину V3, получим дерево, представленное на рис. 6.40.

Если подвесим дерево за вершину v4, оно будет выглядеть так, как показано на рис. 6.41

Вершина в самой верхней части каждого из изображений называется корнем дерева. Если корень дерева определен, дерево называется корневым деревом.

Если корень выбран, уровень вершины v определяется длиной единственного пути из корня в вершину v. Высотой дерева называется длина самого длинного пути от корня дерева до листа.

Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

Цикломатическим числом (g) графа называется минимальное количество ребер, которое необходимо изъять из графа, чтобы он стал деревом. Цикломатическое число определяется по формуле:

,

где N – количество ребер,

k – количество вершин.

Пример:


Дата добавления: 2015-09-27 | Просмотры: 339 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.004 сек.)