20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

31 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

3484. Лекційний курс з основ фізики 2.71 MB
  Тема 1. Фізичні основи механіки. Кінематика Лекція 1. Основи кінематики поступального та обертального рухів Основні визначення В механіці розглядають механічний рух. Під механічним рухом розуміють зміну з часом положення тіла відносно інших тіл в пр...
3485. Измерение скорости пули с помощью физического маятника 55.8 KB
  Измерение скорости пули с помощью физического маятника Цель работы: с помощью физического маятника определить скорость пули. Рабочую формулу для экспериментального определения скорости пули получить исходя из законов сохранения момента импульса и эн...
3486. Определение ускорения свободного падения при помощи оборотного и математического маятников 443.96 KB
  Определение ускорения свободного падения при помощи оборотного и математического маятников, изучение законов колебания маятника, ознакомление с косвенными методами измерения ускорения свободного падения при помощи математического и оборотного...
3487. Бухгалтерский учёт хозяйственных процессов 391 KB
  Бухгалтерский учёт хозяйственных процессов Введение Бухгалтерский учёт представляет собой упорядоченную систему сбора и обобщения информации в денежном выражении об имущес...
3488. Основы бухгалтерского учета и бухгалтерского баланса 203.5 KB
  Принципы бухгалтерского учета При формировании и использовании учетной политики следует соблюдать следующие принципы бухгалтерского учета: Начисление. Доходы признаются, когда они заработаны, а убытки, когда они понесены, т.е. в момент возникновен...
3489. Бухгалтерский учет и аудит. Виды хозяйственного учета 162 KB
  Бухгалтерский учет и аудит Тема 1: общая характеристика и сущность бухгалтерского учета. 1)виды хозяйственного учета. Содержание и функции бухгалтерского Учета 2)задачи и принципы бухгалтерского учета 3)предмет и объект бух учета 4)метод бух.учета 5)классификация имущес...
3490. Бухгалтерский учёт и аудит на предприятии 31.25 KB
  Бухгалтерский учёт и аудит (экзамен) Впервые систематизация приемов бух. учета была проведена францисканским монахом Лукой Пачоли, который большую часть жизни преподавал математику в университетах Балонии, Флоренции и закончил карьеру на почётном по...
3491. Бухгалтерский учёт и аудит в банке 25.6 KB
  Бухгалтерский учёт и аудит в банке Тема 1. Организация бухгалтерского учета в банках. Кредитная организация – это юридическое лицо, которое для получения прибыли как основной цели своей деятельности на основании лицензии Банка России имеет прав...
3492. Учет кассовых операций банка 35.24 KB
  Учет кассовых операций банка Кассовые операции – это операции банка по приему выдачи денег и ценностей клиентам банка. В коммерческом банке обслуживание клиентов производится операционной кассой, в состав которой входит: Приходные кассы...