20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

26 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

27723. Смертная казнь как исключительная мера наказания по УП. Проблемы назначения и применения данного вида наказания 31 KB
  Смертная казнь как исключительная мера наказания по УП. Смертная казнь является исключительной мерой наказания которая заключается в лишении осужденного самого важного блага жизни. 277 295 317 и 357 УК РФ; сфера ее применения ограничена кругом лиц по полу и возрасту; смертная казнь в порядке помилования может быть заменена на пожизненное лишение свободы или лишение свободы на 25 лет; уголовноисполнительным законодательством установлен ряд дополнительных гарантий против исполнения необоснованных смертных приговоров: обязательна...
27725. Совершение преступления группой лиц, группой лиц по предварительному сговору, организованной группой лиц, преступным сообществом (преступной организацией) 29 KB
  Совершение преступления группой лиц группой лиц по предварительному сговору организованной группой лиц преступным сообществом преступной организацией. 35 Преступления совершенные группой лиц подразумевают только соисполнительство без предварительной договоренности о совершении преступления. При соисполнительстве не исключается распределение действий входящих в объективную сторону преступления между соучастниками. Как правило такие преступления совершаются в форме присоединения соисполнителя к противоправному посягательству уже...
27727. Террористический акт (ст. 205 УК) и заведомо ложное сообщение об акте терроризма (ст. 207 УК). Условия освобождения от уголовной ответственности за терроризм. Отличие данного преступления от диверсии 85.5 KB
  3 статьи характеризуется двумя формами вины – прямым умыслом в отношении деяния и неосторожностью в отношении смерти человека или иных тяжких последствий. Угроза совершения взрыва поджога или иных действий устрашающих население и создающих опасность гибели человека причинения значительного имущественного ущерба либо наступления иных тяжких последствий часть 1 статьи 205 УК РФ может быть выражена различными способами например устное высказывание публикация в печати распространение с использованием радио телевидения или иных средств...
27728. Правовой статус иностранных граждан согласно Конституциям Монголии и Российской Федерации (сравнительно-правовое исследование) 50.5 KB
  УланБатор Правовой статус иностранных граждан согласно Конституциям Монголии и Российской Федерации сравнительноправовое исследование В двадцать первом веке веке глобализации мира люди могут свободно ездить работать учиться и жить в открытом обществе.1 Рассматривая вопрос о содержании правового статуса иностранных граждан в Монголии и Российской Федерации целесообразно использовать имеющиеся в юридической литературе наработки по общим проблемам правового положения личности поскольку статус иностранных граждан соотносится со статусом...
27729. Сравнительный анализ Конституции России и США 50.5 KB
  Конституция США не декларирует прав и обязанностей граждан. Декларация полномочий ветвей власти в Конституции США носит более абстрактный характер. Конституция США предусматривает выборную должность вицепрезидента в России эта должность упразднена.