20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

27 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

72676. Улучшение параметров транзисторного стабилизатора с защитой от КЗ с током нагрузки от 3А 512.42 KB
  При перегрузке входа стабилизатора к участку эмиттер-коллектор регулирующих транзисторов будет приложено полное входное напряжение. Поэтому, для повышения надежности данной схемы, максимально допустимое напряжение применяемых транзисторов должно быть, по крайней мере, в 1.5 раза...
72677. Программная реализация метода последовательного перебора 1.55 MB
  В работе имеется 2 главы. Первая глава посвящена обзору численных методов оптимизации функций одной переменной. Во второй главе представлены сведения о программной реализации методов равномерного перебора и последовательного перебора, а также рассмотрено тестирование программ на примере функции.
72678. Изучение и раскрытие теоретических аспектов проблемного обучения в школе 49.98 KB
  Цель курсовой работы: изучить и раскрыть теоретические аспекты проблемного обучения в школе. Задачи курсовой работы: изучить и раскрыть сущность технологии проблемного обучения в учебном процессе; рассмотреть технологию проблемного обучения в учебном процессе на уроках химии; разработать урок по химии...
72679. Разработка модели информационной системы расчета стоимости раскроя листового материала 1.71 MB
  В данном курсовом проекте описывается проектирование модели информационной системы расчета стоимости раскроя листового материала на предприятии ООО НПК Изуран. Целью проекта является разработка модели информационной системы расчета стоимости раскроя листового материала.
72680. Проект системы приточной вентиляции спортзал спортивного комплекса 363.02 KB
  В условиях современного производства и строительства вентиляция и кондиционирование воздуха являются одной из главных мер обеспечивающих наилучшие условия для высокопроизводительного труда повышения творческой активности а также полноценного отдыха людей.
72681. Проектирование технологического процесса изготовления детали “Крышка подшипника” 243.38 KB
  Выбор метода получения и проектирования заготовки Выбор метода обработки поверхностей детали. Выбор методов и средств контроля точности изготовления детали. Вывод по работе Список используемой литературы Приложение Анализ чертежа детали и её служебного назначения.
72682. Павильонная фотосъёмка 2.01 MB
  Количество и мощность применяемых при этом источников света должны соответствовать величине освещенности необходимой для получения высококачественного снимка. В соответствии с ними регулируется сила света осветительных приборов их расстановка что позволяет решать композиционные задачи...
72683. Вручение орденов и медалей Временного правительства и Белого движение в ходе Гражданской войны в России (1917-1922) 49.68 KB
  На разных фронтах Гражданской войны этот вопрос решался по-разному: в некоторых белогвардейских армиях старались обходиться запасами царских орденов и медалей – в армии А.В. Колчака вручались даже ордена Святого Георгия, чего не наблюдалось на других участках Гражданской войны.
72684. Вскрытие и промышленная разработка Тишинского месторождения 688.54 KB
  При выборе методики разведки Тишинского месторождения особенно на первых этапах изучения – до 1964 года наряду с геологическими особенностями решающее влияние имел фактор времени необходимость быстрейшего ввода его в эксплуатацию и геоморфологические условия.