20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

29 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

10529. Коммерческие условия пассажирских перевозок 32.5 KB
  Коммерческие условия пассажирских перевозок. Три категории: Богатые. Курьеры. Бедные. Не выдержало конкуренции с авиацией. Появилось два вида: паромное круизное. Особенность паромов короткие морские. Каюты минимальных р...
10530. Социальная педагогика 27 KB
  Педагогическая деятельность это одна из сторон профессиональной деятельности специалиста по социальной работе. Педагогическая деятельность специалиста направлена на превращение неуправляемой неорганизованной деятельности члена социального сообщества в управляему...
10531. Социальная педагогика: предмет и основные понятия 109 KB
  Социальная педагогика: предмет и основные понятия План. 1. Основная функция и предмет педагогики. 2. Основная функция и предмет социальной педагогики. 3. Основные понятия социальной педагогики. 1. Основная функция и предмет педагогики. Область любой проф
10532. Российский менталитет. Его сущность и национальная специфика 40.5 KB
  Российский менталитет. Его сущность и национальная специфика. Идеалы равенства и социальной справедливости в российской ментальности. 1 равенство и социальная справедливость а также на настороженное отношение к частной собственности и особенное отношение к деньгам...
10533. Структура и механизм функционирования индивидуального сознания. Понятия: хитрость и мудрость; разум и интеллект 58 KB
  Структура и механизм функционирования индивидуального сознания. Понятия: хитрость и мудрость; разум и интеллект Структура сознания. Понятие сознание не однозначно. В широком смысле слова под ним имеют в виду психическое отражение действительности независимо от того...
10534. Идеалистическое и материалистическое понимание общественной жизни. Гегель и Маркс 39.5 KB
  Идеалистическое и материалистическое понимание общественной жизни. Гегель и Маркс. Материалистическое понимание общества. Марксистский философский материализм неизбежно приводит к материалистическому пониманию истории к революционнокоммунистическим выводам. В
10536. Закономерность и свободная деятельность людей. Фатализм и Волюнтаризм 38 KB
  Закономерность и свободная деятельность людей. Фатализм и Волюнтаризм. ВОЛЮНТАРИЗМ философская мировоззренческая позиция суть Крой состоит в признании воли в качестве первоосновы сущего либо акта волнения в качестве высшего принципа бытия. Термин €œВ.€ введен
10537. Западноевропейская средневековая ученость 57.5 KB
  Западноевропейская средневековая ученость В отличие от арабской культуры высокий уровень которой позволил сразу по достоинству оценить достижения античности европейские варвары захватившие Западную Римскую империю находились в этот период на более низком уровне