20508

Неорієнтовані та орієнтовані графи

Доклад

Информатика, кибернетика и программирование

Граф це сукупність об'єктів із зв'язками між ними. Об'єкти розглядаються як вершини або вузли графу а зв'язки як дуги або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.

Украинкский

2013-07-25

27 KB

31 чел.

Неорієнтовані та орієнтовані графи.

Граф — це сукупність об'єктів із зв'язками між ними.

Об'єкти розглядаються як вершини, або вузли графу, а зв'язки — як дуги, або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.

Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами.

Неорієнтований граф

Граф або неорієнтований граф  — це впорядкована пара , для якої виконуються наступні умови:

— множина вершин або вузлів,

— множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин, які називають ребрами.

(і так само ) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.

Орієнтований граф

Граф, який містить тільки ребра називається неорієнтованим, який містить тільки дуги — орієнтованим. Граф, що має як ребра так і дуги, називається мішаним. Якщо пара вершин сполучається кількома ребрами чи дугами одного напрямку, то ребра (дуги) називають кратними (паралельними). Дуга чи ребро що сполучає вершину саму із собою називається петлею. Граф без кратних дуг і петель називається простим.

Вершини сполучені ребром чи дугою називають суміжними, також називають суміжними ребра, що мають спільну вершину. Ребро (чи дуга) і її вершина називаються інцидентними. Ребро (u, v) з'єднує вершини u і v, дуга (u, v) починається у вершині u і закінчується у вершині v.

Кожен граф можна відобразити в евклідовому просторі множиною точок, які відповідають вершинам, сполучених лініями, що відповідають ребрам (дугам).


 

А также другие работы, которые могут Вас заинтересовать

73637. Співвідношення культури та цивілізації 1.5 MB
  Співвідношення культури та цивілізації Певні теоретичні міркування саме під таке розуміння цивілізованості підвів американський соціолог та культуролог Л. Морган намагався відрізняти давні перші цивілізації від сучасної цивілізації яка У базується на наукових знаннях та технічних досягненнях Упередбачає високий рівень культури релігійної свободи демократичних прав правового регулювання міжнародних відносин. Досить резонансною та багато в чому пророчою постала книга Освальда Шпенглера Занепад Європи в якій цивілізація...
73638. Статистика населения 160.5 KB
  Для полного и точного учета численности населения необходимо определить границы территории, на которой учитывается население, и установить время, к которому относятся данные о численности населения. Учет населения производится по населенным пунктам
73639. Статистика объема и состава национального богатства 98 KB
  Национальное богатство (НБ) – важнейшая социально-экономическая категория, используемая для оценки экономического потенциала и уровня экономического развития страны.
73640. Статистика основных фондов 169 KB
  Основные фонды представляют собой совокупность потребительных стоимостей производственного и непроизводственного назначения, которые функционируют в экономике на протяжении ряда лет и, постепенно изнашиваясь
73641. Статистика национального богатства 112 KB
  Статистика оборотных фондов Понятие и состав оборотных фондов. Показатели объема и структуры оборотных фондов. Показатели использования и динамики материальных оборотных фондов Показатели оборачиваемости оборотных средств. Понятие и состав оборотных фондов Оборотные фонды важная часть национального богатства страны его наиболее мобильный постоянно возобновляемый элемент.
73642. Память. Типовые структуры и функциональные узлы микросхем памяти 1.32 MB
  Каждый код хранится в отдельном элементе памяти называемом ячейкой памяти. Основная функция любой памяти состоит в выдаче этих кодов на выходы микросхемы по внешнему запросу. Основной параметр памяти ее объем то есть количество кодов которые могут в ней храниться и разрядность этих кодов. Для обозначения количества ячеек памяти используются следующие специальные единицы измерения: 1К это 1024 то есть 210 читается кило или ка примерно равно одной тысяче; 1М это 1048576 то есть 220 читается мега примерно равно одному...
73644. Реформирование и адаптация предприятия к новым условиям хозяйствования 78 KB
  Реформирование и развитие предприятий промышленного комплекса. Проблемы реформирования и адаптации предприятий к новым условиям хозяйствования. Управление предприятием при его реформировании и реабилитации.
73645. Интерфейс ведения журнала кардиологических операций 969 KB
  Компьютеризация медицины идет по самым разным направлениям. На данный момент налицо все технические предпосылки для этого - наличие надежных сетей, серверов, компьютеризированного медицинского инструментария и пр. Большое число медицинских работников активно использует в своей работе самые разнообразные возможности вычислительной техники.