Композиция графиков дискретная математика

Композиция графиков дискретная математика

Проекция множества определена только для множеств, элементами которого являются кортежи одинаковой длины.

Проекцией множества называется множество проекций соответствующих кортежей.

Пр А3,1 не определена.

График и свойства графика

Графиком называется множество пар. Графики могут задаваться :

перечислением:

описанием свойств:

График P -1 называется инверсией графика P, если он состоит из инверсий пар графика P.

График называется симметричным, если вместе с каждой парой он содержит её инверсию.

(27)

Диагональным называется график вида:

, (28)

Композицией графиков называется график R, такой что для любой пары R есть такой элемент z, что P, а Q.

, (29)

PQ= .

2. Пусть заданы графики P и Q:

Рис 5. Композиция графиков.

Свойства графиков.

Функциональным графиком называется график, который не содержит пары с одинаковыми первыми и различными вторыми компонентами.

Инъективным графиком называется график, который не содержит пары с одинаковыми вторыми и различными первыми компонентами.

Рис 6. Примеры графиков.

P1График функциональный, но не инъективный.

P2График инъективный, но не функциональный.

P3 График функциональный и инъективный.

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

Рис 7 . Примеры графиков.

P1График функциональный, но не инъективный.

P2График инъективный, но не функциональный.

P3 График функциональный и инъективный.

Прямое (декартовое) произведение множество.

Прямым (декартовым) произведением множества и множестваназывается множество пар таких, что:

, (29)

Пусть заданыи:,. Тогда прямое (декартовое) произведение этих множеств может быть представлено графически:X=

Рис. 8 График прямого произведения множеств и:

Пусть заданыи:,. Тогда прямое (декартовое) произведение этих множеств представляет шахматную доску.

Соответствия.

Соответствием называется тройка вида . При этом— область отправления (определения),— область прибытия (значений),— график соответствия.

Поскольку соответствия можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) можно применить и к соответствиям. Заметим, что, говоря о дополнении соответствия из Л в В, мы имеем в виду дополнение до универсального соответствия из A в В, т.е. до декартова произведения А × В. Естественно, что и равенство соответствий можно трактовать как равен- равенство множеств.

В то же время на соответствия можно распространить операции, определяемые для отображений. Мы рассмотрим здесь две такие операции.

Композиция соответствий. Следуя аналогии с композицией отображнений, композицией (произведением) соответствий р ⊆ А×В и σ ⊆ В×С называют соответствие

Поясним построение композиции двух соответствий. Обратимся сначала к отображениям (как частным случаям соответствий). Пусть заданы отображения (возможно, частичные): f из А в В и g из В в С. Композиция* fºg определяется как отображение из А в С, задаваемое формулой у = g(f(x)). Тем самым задается график отображения fºg, т.е. множество упорядоченных пар (x, у), таких, что у = g(f(x)). При этом упорядоченная пара (x, у) будет принадлежать графику отображения fºg, если и только если найдется элемент z ∈ В, такой, что z = f(x) и у = g(z). Таким образом, график композиции отображений /ид есть

* Необходимо заметить, что в [I] запись gº f(x) означает g(f(x)), т.е. отображения в композиции пишутся в порядке, обратном тому, в каком они применяются. Мы же будем везде использовать запись fºg, полагая, что fºg(x) = g(f(x)) и порядок записи отображений в композиции совпадает с порядком их применения. Это обусловлено тем, что композиция отображении определяется нами как частный случай композиции соответствий, при записи которой естественным оказывается именно такой порядок.

Легко видеть, что (1.4) есть частный случай (1.3). Отметим, что при построении композиции отображений обычно предполагают, что пересечение области значений отображения f и области определения отображения д не пусто (R(f) ∩ D(g) ≠ 0), поскольку в противном случае композиция была бы пуста. Для отображений, не являющихся частичными, R(f) ⊆ D(g), так как D(g) = В. Поэтому в данном случае пересечение R(f) ∩ D(g) всегда не пусто.

Полезно отметить также, что если f и g — биекции, то и композиция их тоже будет биекцией.

Вернемся к рассмотрению композиции соответствий рºσ. Полагая, что область определения D(p) соответствия р не пуста, возьмем произвольный элемент х ∈ D(p). Пусть сечение р(х) ⊆ B соответствия p не пусто и найдется такой элемент z ∈ р(x), что сечение σ(z) ⊆ C также не пусто. Тогда непустое множество <(x, t): t ∈ σ(z)>будет подмножеством сечения соответствия роа в точке х. Сечением соответствия роа в точке х будет непустое в силу сделанных предположений множество всех таких упорядоченных пар (x, t) ∈ А × С, что х ∈ D(p), a t ∈ σ(z) для некоторого z ∈ р(х). Говоря неформально, нужно перебрать все элементы z из сечения р(х). Таким образом, различие в построении композиции соответствий и композиции отображений заключается в том, что „промежуточный" элемент z в общем случае не единственный и каждому такому элементу также ставится в соответствие не единственный элемент у ∈ С.

Пример 1.8. Соответствие р возьмем из примера 1.3. Соответствие σ зададим как соответствие из множества грамм 1, n2, n3, n4, n5> в множество заказчиков программного обеспечения <З1З2З3З4>. Пусть

сечение композиции по элементу И. Рассуждая аналогично, получим (р॰σ)(П) = <З14> и (р॰σ)(С) = <З13>.

Построение графа композиции р॰σ проиллюстрировано на рис. 1.3. #

Отметим, что область определения композиции соответствий содержится в области определения первого соответствия, а область значений композиции соответствий — в области значений второго соответствия. Из приведенных рассуждений следует, что для того, чтобы композиция соответствий была отлична от пустого соответствия, необходимо и достаточно, чтобы пересечение области значений первого соответствия и области определения второго соответствия было не пусто.

К определению композиции соответствий можно подойти с более общих позиций. Пусть p⊆A×B и σ⊆C×D. При этом на множества A, B, С и D априори не накладывается никаких органичений. Композиция р॰σ соответствий р и σ в этом случае также определяется соотношением (1.3). Чтобы такая композиция была отлична от пустого соответствия, необходимо и достаточно выполнение условия R(p)∩D(σ) ≠ ∅. В частности, р॰σ = ∅ всякий раз, когда В ∩ С = ∅.

Пример 1.9. Рассмотрим соответствие

из множества А = <1,2,3>в множество В = <а, b, d>и соответствие

из множества С = в множество D = <е, f>. В данном случае В ∩ С ≠ ∅, но τ ॰ φ = ∅, поскольку R(τ) = , D(φ) = и R(τ)∩D(φ)=∅. #

Заметим, что композиция соответствий р ⊆ A × B и σ ⊆ С × D не коммутативна, т.е. в общем случае рост р ॰ σ ≠ σ ॰ р, поскольку р ॰ σ ⊆ A × D, а σ ॰ р ⊆ C × B.

Бинарное отношение на множестве является частным случаем соответствия. Для двух бинарных отношений р и σ, заданных на множестве A, их композиция р ॰ σ (1.3) как соответствий является бинарным отношением на том же множестве А. В этом случае говорят о композиции бинарных отношений на множестве А.

Композицию рр бинарного отношения р на некотором множестве с самим собой называют квадратом бинарного отношения р и обозначают р 2 .

Рассмотрим пример построения композиции бинарных отношений на множестве и покажем, что в общем случае для двух бинарных отношений τ и φ также имеет место неравенство τ ॰ φ ≠ φ ॰ τ, хотя обе композиции, в отличие от аналогичных композиций двух произвольных соответствий, заданы на одном и том же множестве.

Читайте также:  Ласковым словом и камень растопишь синтаксический разбор

Приведем некоторые свойства композиции соответствий:

Эти свойства нетрудно доказать методом двух включений. Рассмотрим в качестве примера доказательство свойства 3. Пусть некоторая упорядоченная пара (x, у) принадлежит композиции p ॰ (σ ∪ τ). Тогда, согласно (1.3), найдется такой элемент z, что (x, z) ∈ р и (z, у) ∈ σ ∪ τ. Последнее означает, что (z, у) ∈ σ или (z, у) ∈ τ. Таким образом, для элемента z имеем (x, г) ∈ р и (z, у) ∈ σ или (x, z) ∈ р и (z, у) ∈ τ. Первая альтернатива имеет место при (x, у) ∈ р ॰ σ, а вторая — при (x, у) ∈ р ॰ τ, что означает (x, у) ∈ р ॰ σ ∪ р ॰ τ. Тем самым включение р ॰(σ ∪ τ) ⊆ р ॰ σ ∪ р ॰ τ доказано.

Доказательство включения р ॰ σ ∪ р ॰ τ ⊆ р ॰ (σ ∪ τ) запишем коротко, используя логическую символику:

В данном случае доказательства двух включений не совсем симметричны: элементы u и v во второй части доказательства не обязаны совпадать.

Замечание 1.4. В тождестве, выражающем свойство 3, нельзя вместо объединения поставить пересечение, так как в этом случае тождество нарушится. Можно доказать, что сохранится лишь включение

а обратное включение в общем случае не имеет места. #

Анализ свойств 2 и 4 показывает, что роль пустого соответствия аналогична роли нуля при умножении чисел, а диагональ множества А играет роль, аналогичную роли единицы, на множестве всех бинарных отношений на А.

Обратное соответствие. Соответствие, обратное к соответствию р ⊆ А × В, есть соответствие из В в А, обозначаемое р -1 и равное, по определению, р -1 = <(у, х): (x, у) ∈ р>.

Для соответствия г из примера 1.3

Обратное соответствие обладает следующими легко проверяемыми свойствами:

Для бинарного отношения р на множестве А обратное соответствие есть бинарное отношение на том же множестве. В этом случае говорят о бинарном отношении р -1 на множестве А, обратном к р.

Заметим, что соответствия рр -1 и р -1 ॰р в общем случае не совпадают. Даже для бинарного отношения р на множестве А рр -1 ≠р -1 ॰р, а также рр -1 ≠idA и р -1 ॰р≠idA.

Например, для бинарного отношения р = <(3,1), (4,1), (4,2)>на множестве А = <1,2,3,4>графы самого отношения, обратного отношения р -1 , композиций рр -1 и р -1 ॰р представлены на рис. 1.5.

Если а: A→ В — отображение, то оно является соответствием. Обратное к а соответствие из В в А в общем случае не является отображением. Действительно, соответствие f -1 , обратное к f, состоит из всех упорядоченных пар вида (f(x), x), х∈А. Поскольку в общем случае могут найтись такие два различных элемента х и x’, что f(x) = f(x’), то соответствие f -1 в общем случае не будет функционально по второй компоненте и поэтому не будет отображением. Если отображение f тивно, то обратное соответствие есть частичное отображение из В в А. Если отображение f биективно, то обратное соответствие является отображением из В в А, причем имеют место равенства

Отображение f -1 в этом случае называют отображением, обратным к f.

Ограничение соответствия. Пусть р ⊆ А × В — соответствие из А в В и С ⊆ A, D ⊆ В. Ограничением соответствия р на подмножества С и D (или (С, D)-ограничением соответствия р) называется соответствие из С в D обозначаемое р|C,D) такое, что

Таким образом, (С, D)-ограничение соответствия р есть „то же самое" соответствие р, но из последнего берутся только упорядоченные пары, первая компонента которых принадлежит подмножеству С, а вторая — подмножеству D. Можно записать

Так, „малый" арксинус, т.е. функция у = arcsinx, есть ограничение „ большого" арксинуса у — Arcsin x, который является соответствием на подмножества [—1,1] и [-π/2,π/2].

Рассмотрим некоторые важные частные случаи ограничений соответствий (в частности, бинарных отношений и отображений).

Всякое (С, В)-ограничение соответствия р ⊆ А × В будем называть сужением соответствия р на подмножество С (коротко — С-сужением соответствия р), а всякое (С, p(С))-ограничение соответствия рстрогим сужением соответствия р на подмножество С (строгим С-сужением соответствия р). С-сужения соответствия р будем обозначать р|C, а строгое сужение — р|॰C соответственно.

Полезно заметить, что для любого отображения f: А → В строгое сужение f|॰A есть сюръекция А на f(A). Если, сверх этого, f является инъекцией, то f|॰A есть биекция А на f(A). Допуская некоторую вольность речи*, можно сказать, что любое отображение сюръективно отображает свою область определения на свою область значений, в частности, любая инъекция устанавливает взаимно однозначное соответствие между областью определения и областью значений. Так, функция у = sinx сюръективно отображает множество ℝ всех действительных чисел на отрезок [—1,1], а любая показательная функция биективно отображает ℝ на подмножество всех положительных действительных чисел.

Для бинарного отношения р ⊆ А 2 и любого подмножества М ⊆ А (М, М)-ограничение бинарного отношения называют ограничением бинарного отношения р на подмножество М и обозначают р|M. Можно записать р|M = р∩М 2 .

* Вольность состоит в томб что мы отождествляем функцию а с функцией f|॰A.

Рассмотрим, например, отношение естественного порядка ≤ на множестве действительных чисел [I]. Тогда отношение ≤| = <(m, n): m ≤ n; m, n ∈ ℤ>есть ограничение этого порядка на подмножество целых чисел. Но ни в коем случае нельзя путать это отношение с ℤ-сужением отношения ≤! Это последнее состоит из всех таких упорядоченных пар (m, x), что m ∈ ℤ, x ∈ ℝ и m ≤ x, т.е. вторая компонента пары может быть произвольным действительным числом, не меньшим заданного целого m.

В математике , и более конкретно в теории графов , А граф представляет собой структуру , в размере набора объектов , в которых некоторые пары объектов находятся в каком — то смысле «связаны». Эти объекты соответствуют математическим абстракциям , называемых вершинами (также называемых узлами или точками ) , и каждым из смежных пар вершин называются ребром (также называется дуга или линия ). Как правило, график , изображен в схематическом виде в виде набора точек для вершин, соединенных линиями или кривыми для краев. Графики являются одним из объектов изучения дискретной математики .

Края могут быть направлены или неориентированный. Например, если вершины представляют собой людей на вечеринке, и есть ребро между двумя людьми , если они пожать друг другу руки, то этот граф неориентированный , потому что любой человек может пожать друг другу руки с человеком B только если B и пожимает руки . В противоположность этому , если любое ребро от человека А к человеку B соответствует восхищаясь с B , то этот график направлен, потому что восхищение не обязательно возвратно — поступательное движение. Первый тип графа называется неориентированный граф , а ребра называются неориентированных ребер в то время как последний тип графа называется ориентированный граф , а ребра называются ориентированными ребрами .

Читайте также:  Я хочу чтобы было чисто как пишется

Графики являются основным предметом изучались теории графов . Слово «граф» был впервые использован в этом смысле по Джеймс Джозеф Сильвестр в 1878 году.

содержание

Определения

Определения в теории графов различаются. Ниже приведены некоторые из наиболее основных способов определения графиков и связанных с ними математических структур .

график

В одном очень общем смысле этого термина, А граф является упорядоченная пара G = ( V , E ) , содержащее множество V из вершин , узлов или точек вместе с набором Е из ребер , дуг или линий , которые являются 2-элементные подмножества из V (т.е. ребро связанно с двумя вершинами, и ассоциация принимает форму неупорядоченной пары вершин). Для того, чтобы избежать неоднозначности, этот тип графика может быть описана именно как неориентированный и простой .

Другие чувства графа вытекает из различных концепций набора кромок. В еще одном общей концепции, Е представляет собой набор вместе с отношением частоты , который связывает с каждым ребром две вершины. В другом обобщенном понятии, Е представляет собой мультимножество неупорядоченных пар (не обязательно различных) вершин. Многие авторы называют эти типы объектов мультиграфов или псевдографов.

Все эти варианты и другие будут более подробно описаны ниже.

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

В и Е , как правило , принимаются конечными, и многие из хорошо известных результатов не являются истинными (или весьма различны) для бесконечных графов , так как многие из аргументов потерпеть неудачу в бесконечном случае . Кроме того, V часто предполагается непустым, но Е позволено быть пустым множеством. Порядок графа называется | V |, число его вершин. Размер графа называется | E |, его количество ребер. Степень или валентность вершины есть число ребер , которые подключаются к нему, где ребро , которое соединяется с вершиной в обоих концах (а петли ) считаются дважды.

Для ребра < х , у >, теоретики графа обычно используют несколько короче обозначение х .

Примыкание отношение

Ребра Е неориентированного графа G индуцирует симметричное бинарное отношение

на V , что называется отношение смежности из G . В частности, для каждого ребра < х , у >, вершины х и у , называются смежными друг с другом, который обозначается х

Типы графиков

Различие в терминах основного определения

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

неориентированный граф

Неориентированный граф представляет собой график , в котором ребро не имеет ориентаций. Ребро ( х , у ) совпадает с краем ( у , х ) . То есть, они не упорядоченные пары, но неупорядоченные пары-то есть, наборы двух вершин < х , у > (или 2- мультимножеств в случае петель ). Максимальное число ребер в неориентированном графе без петли п ( п — 1) / 2 , где п есть число узлов в графе.

Направленный граф

Ориентированный граф или орграф представляет собой график , в котором ребра имеют ориентацию. Это записывается в виде упорядоченной пары G = ( V , ) (иногда G = ( V , E ) ) с

  • Вмножестве , чьи элементы называются вершины , узлы , или точки ;
  • Множество упорядоченных пар вершин, называемые стрелок , направленные ребра (иногда просто кромки с соответствующим набором именем Е вместо A ), направленные дугами , или направленных линиями .

Стрелка ( х , у ) считается направленными от й к у ; у называется головой и х называется хвостом стрелки; у называется быть прямым преемником по х и х называется быть прямым предшественником из г . Если путь ведет от й к у , то у называются быть правопреемником по й и достижим из х , а х называются быть предшественником из г . Стрелка ( у , х ) называется перевернутая стрелка из ( х , у ) .

Ориентированный граф G называется симметричным , если для каждой стрелки в G , соответствующая перевернутая стрелка также принадлежит G . Симметричный loopless ориентированный граф G = ( V , ) эквивалентен простой неориентированный граф G ‘ = ( V , E ) , где пары обратных стрелок в А соответствуют один к одному с краями в Е ; Таким образом , число ребер в G ‘ является | E | = | | / 2 , то есть половина число стрелок в G .

ориентированный граф

Ориентированный граф представляет собой ориентированный граф , в котором не более чем один из ( х , у ) и ( у , х ) может быть стрелка графа. То есть, это ориентированный граф , который может быть выполнен в виде ориентации неориентированного графа. Тем не менее, некоторые авторы используют «ориентированный граф» означает то же самое , как «ориентированный граф».

Смешанный график

Смешанный график представляет собой график , в котором некоторые ребра могут быть направлены и некоторые из них могут быть неориентированными. Это записывается в виде упорядоченной тройки G = ( V , E , ) с V , E , и , как определено выше. Направленные и ненаправленные графы являются частными случаями.

мультиграф

Несколько ребер два или более реберкоторые соединяют одните же две вершины. Цикл ребро (направленный или неориентированный)который соединяет вершину самусобой; оно может быть разрешено или нет,зависимости от применения. В этом контексте, ребро с двумя разными концами называются ссылкой .

Мультиграф , в отличие от простого графа , неориентированный граф , в котором несколько ребер (а иногда и петля) допустимы.

Если графы определяются таким образом , чтобы запретить оба кратные ребра и петли, Мультиграф часто определяются означает график , который может иметь как несколько ребер и петли, хотя многие используют термин псевдограф для этого значения. Если графы определяются таким образом , чтобы позволить как несколько ребер и петель, Мультиграф часто определяется означает граф без петель.

Простой график

Простой граф неориентированный граф с ни кратных ребер , ни петель . В простом графе ребра образуют набор (а не мультимножество ) , и каждое ребро является неупорядоченной парой различных вершин. Таким образом, мы можем определить простой график , чтобы быть множество V вершин вместе с набором Е ребер, которые являются 2-элементные подмножества V .

В простом графе с п вершинами, степень каждой вершины не превосходит п — 1 .

Колчан

Колчан или multidigraph является направленным мультиграфом. Колчан может быть направлена петля в нем. Таким образом, колчан представляет собой набор V вершин, множества Е ребер и двух функций , . Карта с присваивает каждый край его источник (или хвост ), в то время как отображение т присваивает каждое ребро его целевой (или головка ). s : Е → В < Displaystyle с: Е к V> T : Е → В < Displaystyle т: Е к V>

взвешенный граф

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

Полуребра, свободные края

В некоторых ситуациях это может быть полезно , чтобы края с только один концом, называемой полуреброй , или никаких концов, называемых свободными краями ; Смотрите статьи Подписанные графики и предвзято графики .

Читайте также:  Как изменить название процессора в свойствах системы

Важные классы графа

Обычный график

Регулярный граф представляет собой график , в котором каждая вершина имеет такое же число соседей, то есть, каждая вершина имеет ту же степень. Регулярный граф с вершинами степени к называется к -регулярной граф или регулярный граф степени к .

Полный график

Полный граф представляет собой график , в котором каждая пара вершин соединена ребром. Полный граф содержит все возможные ребра.

конечный граф

Конечный граф представляет собой график , в котором множество вершин и множество ребер имеют конечные множества . В противном случае, он называется бесконечным графом .

Наиболее часто в теории графов, подразумевается, что графики обсуждавшиеся конечны. Если графики безграничны, что, как правило, специально оговоренные.

связной граф

В неориентированном графе, неупорядоченная пара вершин < х , у > называются связной если путь ведет от й к у . В противном случае, неупорядоченная пара называется отсоединена .

Связный граф представляет собой неориентированный граф , в котором каждая неупорядоченная пара вершин в графе соединена. В противном случае это называется несвязный граф .

В ориентированном графе, упорядоченная пара вершин ( х , у ) называется сильно связной , если направленный путь ведет от й к у . В противном случае, упорядоченная пара называется слабо связная , если неориентированный путь ведет от й к у после замены все его ориентированных ребер с неориентированными ребрами. В противном случае, упорядоченная пара называется отсоединена .

Сильно связный граф представляет собой ориентированный граф , в котором каждая упорядоченной пара вершин в графе сильно связана. В противном случае это называется слабо связный граф , если каждая упорядоченная пара вершин в графе слабо связаны между собой . В противном случае это называется несвязный граф .

К-вершинного графа соединены или к-кра-связный граф представляет собой график , в котором нет набор к — 1 вершин (соответственно ребер) не существует , что, в случае их удаления, разъединяет граф. К -vertex-связный граф часто называют просто к-связным графом .

двудольный граф

Двудольный граф является простой граф , в котором множество вершин может быть разбивается на два множества, W и X , так , чтобы никакие две вершины из W имеют общий край и никакие две вершины в X имеют общий край. В качестве альтернативы, он представляет собой график с хроматическим числом 2.

В полной двудольный граф , множество вершин является объединением двух непересекающихся множеств, W и X , так что каждая вершина W смежна с каждой вершиной в X , но нет никаких ребер в пределах W или X .

Путь графа

Путь графа или линейный граф порядка п ≥ 2 представляет собой график , в котором вершины могут быть перечислены в порядке V 1 , V 2 , . v п такие , что ребра являются < v I , v я + 1 > , где я = 1, 2, . п — 1. графы путь можно охарактеризовать как связных графов , в которых степень всех , кроме двух вершин 2 и степень двух оставшихся вершин равно 1. Если путь графа происходит как подграфа другого графа, это путь , в этом графике.

Planar график

Плоский граф представляет собой график , чьи вершины и ребра могут быть сделаны в одной плоскости таким образом, что никакие два из ребер не пересекаются.

Цикл график

Цикл графа или круговая диаграмма порядка п ≥ 3 представляет собой график , в котором вершины могут быть перечислены в порядке V 1 , V 2 , . v п такие , что ребра являются < v я , v я + 1 > , где я = 1, 2, . п — 1, а также ребро < v п , v 1 >. Графики цикла можно охарактеризовать как связные граф , в которых степень всех вершин равно 2. Если цикл граф происходит в подграфа другого графа, то есть цикл или контур в этом графике.

дерево

Дерево является связным графом без циклов.

Лес представляет собой граф без циклов, т.е. несвязного объединения одного или нескольких дерев.

Дополнительные классы

Более сложные виды графов:

Свойства графиков

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

Граф только с одной вершиной и без каких — либо ребер называется тривиальным графиком . Граф только с вершинами и без ребер известно как безреберный граф . Граф без вершин и без ребер иногда называют нулевым графом или пустым графом , но терминология не соответствует и не всем математикам позволяют этот объект.

Как правило, вершины графа, по своей природе в качестве элементов множества, различимы. Этот вид графа можно назвать вершиной меченными . Тем не менее, для многих вопросов, лучше рассматривать вершины неразличимыми. (Конечно, вершины могут быть еще различимы свойствами самого графа, например, по номерам инцидентных ребер.) Те же замечания относятся к краям, поэтому графы с помеченными ребрами называются краем меченными . Графы с ярлыками к краям или вершинам более обычно обозначают как меченые . Следовательно, графы , в которых вершины неразличимы и ребра неразличимы называется непомеченным . (Обратите внимание , что в литературе термин маркированы может применяться к другим видам маркировки, кроме того , что служит только для различения разных вершин и ребер.)

Категория всех графиков является категорией ломтика Set ↓ D , где D : Set → Set является функтор принимает множество лет до с × с .

Примеры

  • Диаграмма справа представляет собой графическое изображение на следующем графике:

V = <1, 2, 3, 4, 5, 6 >; Е = <<1, 2>, <1, 5>, <2, 3>, <2, 5>, <3, 4>, <4, 5>, <4, 6>> .

  • В теории категорий , малая категория может быть представлена в виде направленного мультиграфом , в котором объекты категорий представлены вершинами и морфизмах , как направленные ребра. Затем функторы между категориями вызывают некоторые, но не обязательно все, из орграфа морфизмов графа.
  • В информатике , ориентированные графы используются для представления знаний (например, концептуальный граф ), конечные автоматы , а также множество других дискретных структур.
  • Бинарное отношениеR на множестве X определяет ориентированный граф. Элемент х из X является прямым предшественником элемента у из X тогда и только тогда , когда хКа .
  • Ориентированный граф может моделировать информационную сеть , такие как Twitter , с одним пользователем следующих другим.
  • В частности , обычные примеры ориентированных графов задаются графами Кэлей конечно порожденных групп, а также шрейеровы смежных классов графов

операции Graph

Есть несколько операций, которые производят новые графики с исходных, которые могут быть классифицированы по следующим категориям:

Обобщения

В гиперграфе , край может присоединиться к более двух вершинам.

Неориентированный граф можно рассматривать как симплициальный комплекс , состоящий из 1- симплексов (края) и 0-симплексов (вершины). Таким образом , комплексы являются обобщением графов , так как они позволяют более-симплексов.

Каждый график приводит к матроиду .

В модели теории , график просто структура . Но в таком случае, не существует каких — либо ограничений по количеству ребер: это может быть любое кардинальное число , см непрерывный график .

В вычислительной биологии , анализ мощности графика вводит мощность графику в качестве альтернативного представления неориентированных графов.

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

Ссылка на основную публикацию
Клавиатура не печатает в ворде что делать
Будучи периферийной техникой, клавиатура представляет собой довольно надежное устройство. Иногда в силу тех или иных факторов она начинает сбоить. Что...
Как уменьшить масштаб при печати word
По умолчанию новый документ в Ворд 2007 создается с масштабом 100%. Напомним, что движок изменения масштаба документа находится в правом...
Какая плита лучше гефест или горение
Европейская компания Gorenje предлагает большой выбор электрических плит. Они наделены разнообразными опциями, которые упрощают приготовление пищи, повышают ее вкусовые качества....
Кнопка novo на ноутбуке lenovo что это
Из этой статьи вы узнаете несколько способов открыть настройки БИОСа на ноутбуках Lenovo, решение возможных проблем и способ входа в...
Adblock detector