20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

30 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

51161. ОПЕРАЦИОННЫЙ БЛОК МИКРОПРОГРАММИРУЕМОГО ПРОЦЕССОРА 127.5 KB
  Определить количество нулей в коде числа. Используемые регистры R0=Число в котором будет определяться колво нулейC000 h R2=10 h R3=0 Тесты: R0=C000 R2=000E; R0=FFFF R2=0000; R0=0000 R2=0010; R0=FBE R2=0004; Выводы: В данной работе был изучен операционного блока на уровне структурной схемы так же я ознакомился с составом микрокоманд и порядком их выполнения с составлением и отладкой микропрограммы. Был разработан и реализован алгоритм позволяющий определить количество нулей в коде числа и в соответствии с ним написана микропрограмма.
51162. Исследование параметров воздуха рабочей зоны и защиты от тепловых излучений 42.9 MB
  Холодный период года период года характеризуемый среднесуточной температурой наружного воздуха равной 10 С и ниже. Теплый период года период года характеризуемый среднесуточной температурой наружного воздуха выше 10 С. Среднесуточная температура средняя величина температуры наружного воздуха измеренная в определенные часы суток через одинаковые интервалы времени.
51163. Розвязування задач теорії прийняття рішень за допомогою дерев рішень 1.39 MB
  Мета: навчитися розвязувати задачі теорії прийняття рішень за допомогою дерев рішень Теоретичні відомості Дерево рішень це граф що представляє правила в ієрархічній послідовній структурі де кожному обєкту відповідає єдиний вузол який дає розвязок. Для генерації різних варіантів рішень і їх оцінки найбільше поширення знайшли дерева рішень що містять два типи вершин: вершини в яких рішення приймає експерт ОПР і вершини де рішення приймає випадок виходящі з вершини дуги задають визначені імовірності напрямків прийняття...
51164. ФЛЭШ-ПЯМЯТЬ 362 KB
  В схемах флэш-памяти не предусмотрено стирание отдельных слов, стирание информации осуществляется либо для всей памяти одновременно, либо для достаточно больших блоков. Это позволяет упростить схему ЗУ и позволяет повысить степень интеграции и быстродействия.
51165. Введение в лингвистику 2.86 MB
  Лингвистика как наука о языке возникла лишь в XIX веке, но интерес людей к языку насчитывает уже более двух тысячелетий. Почему столько веков человек пытается познать природу языка. Ведь в отличие от медицины, генетики, химии и других наук успехи лингвистики лишь косвенно связаны с проблемами выживания человеческого рода. Да и научились ли мы лучше понимать друг друга, изучая основное средство общения - язык...
51168. Исследование интегрального датчика температуры LM60 89.22 KB
  Цель: изучить конструкцию интегрального датчика температуры LM60 его свойства применение научиться снимать статистическую характеристику. Вывод: изучили свойства интегрального датчика температуры LM60 его применение научились снимать...
51169. Исследование работы термометра сопротивления 56.06 KB
  Цель: изучить конструкцию термометра сопротивления его свойства применение научиться снимать статистическую характеристику.