20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

31 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

83750. Сравнение The Present Simple и The Present Continuous 204.68 KB
  Цель: более глубокое усвоение знаний, высокий уровень обобщения, систематизации. Задачи: Образовательные: обобщить материал как систему знаний, наглядно показать и закрепить разницу двух настоящих времен. Развивающие: развивать пространственное мышление, выявлять связи, формулировать выводы...
83751. Правовое регулирование единого сельскохозяйственного налога: общие положения, налогоплательщики, основные элементы налога, налоговая декларация 40.66 KB
  ЗАМЕНЯЕТ НАЛОГИ Освобождает от налогов: ОРГАНИЗАЦИИ: налога на прибыль организаций за исключением налога уплачиваемого с доходов по дивидендам и отдельным видам долговых обязательств налога на имущество организаций налога на добавленную стоимость за исключением НДС уплачиваемого при ввозе товаров на таможне а также при выполнении договора простого товарищества или договора доверительного управления имуществом ИНДИВИДУАЛЬНЫЕ ПРЕДПРИНИМАТЕЛИ: налога на доходы физических лиц в отношении доходов от предпринимательской деятельности...
83752. Правовое регулирование упрощенной системы налогообложения: общие положения, налогоплательщики, основные элементы налога, особенности уплаты 42.57 KB
  В связи с применением УСН налогоплательщики освобождаются от уплаты налогов применяемых общей системой налогообложения налога на имущество организаций налога на добавленную стоимость и др.13 НК РФ Переход на УСН с ЕНВД с начала того месяца в котором была прекращена их обязанность по уплате единого налога на вмененный доход п. СТАВКИ И ПОРЯДОК РАСЧЕТА Расчет налога производится по следующей формуле статья 346.
83753. Правовое регулирование системы налогообложения в виде единого налога на вмененный доход для отдельных видов деятельности: общие положения, налогоплательщики, основные элементы налога 40.79 KB
  ЕНВД применяется в отношении отдельных видов предпринимательской деятельности п. Налог на прибыль организаций В отношении прибыли полученной от предпринимательской деятельности облагаемой единым налогом 2. Налог на имущество организаций В отношении имущества используемого для ведения предпринимательской деятельности облагаемой единым налогом 3.
83754. Правовое регулирование системы налогообложения при выполнении соглашений о разделе продукции: общие положения, налогоплательщики, особенности уплаты 41.83 KB
  Система налогообложения при выполнении соглашений о разделе продукции особая система налогообложения специальный налоговый режим применяемый при выполнении соглашений которые заключены в соответствии с Федеральным законом от 30. № 225ФЗ О соглашениях о разделе продукции. Режим применяется в течение всего срока действия соглашения о разделе продукции.
83755. Правовое регулирование транспортного налога: общие положения, налогоплательщики, основные элементы налога, особенности регионального законодательства 42.78 KB
  Налогоплательщиками транспортного налога признаются лица на которых в соответствии с законодательством Российской Федерации зарегистрированы транспортные средства ст. Плательщиками налога также признаются физические лица получившие транспортные средства по доверенности выданной до 29 июля 2002 года. Следовательно по истечении трех лет с момента выдачи доверенности на право владения и распоряжения транспортным средством выданной до 29 июля 2002 года плательщиком транспортного налога признается физическое лицо на которое зарегистрировано...
83756. Правовое регулирование налога на игорный бизнес: налогоплательщики, основные элементы налога, особенности регионального законодательства 41.92 KB
  365 НК РФ Объект налогообложения налогом на игорный бизнес являются ст. Каждый объект налогообложения должен быть зарегистрирован в налоговой инспекции по месту установки не позднее чем за 2 рабочих дня до даты его установки. Регистрация игрового оборудования или пункта приема ставок проводится налоговым органом на основании заявления налогоплательщика с обязательным ой получением выдачей свидетельства о регистрации объекта объектов налогообложения. Любое изменение количества объектов необходимо также зарегистрировать в налоговых органах...
83757. Правовое регулирование налога на имущество организаций: общие положения, налогоплательщик, основные элементы налога, особенности исполнения и уплаты налога 46.96 KB
  1 указанного Федерального закона в отношении имущества используемого ими исключительно в связи с организацией и или проведением XXII Олимпийских зимних игр и XI Паралимпийских зимних игр 2014 года в городе Сочи и развитием города Сочи как горноклиматического курорта. 375 НК РФ определяется как среднегодовая стоимость имущества признаваемого объектом налогообложения. В случае если для отдельных объектов основных средств начисление амортизации не предусмотрено стоимость указанных объектов для целей налогообложения определяется как разница...
83758. Правовое регулирование земельного налога: общие положения, налогоплательщики, основные элементы налога, особенности местного (муниципального) законодательства 43.68 KB
  Плательщики налога Плательщиками налога признаются физические лица обладающие земельными участками признаваемыми объектом налогообложения в соответствии со ст. В отношении земельных участков используемых предназначенных для использования в предпринимательской деятельности налоговая база по налогу и исчисление суммы налога суммы авансовых платежей по налогу производится индивидуальными предпринимателями самостоятельно на основании сведений государственного кадастра недвижимости о каждом земельном участке. Ставки налога Налоговые ставки...