Граф (дискретная математика)

В дискретной математике , а точнее в теории графов , граф — это структура, состоящая из набора объектов, в котором некоторые пары объектов в некотором смысле «связаны». Объекты представлены абстракциями, называемыми вершинами (также называемыми узлами или точками ), и каждая из связанных пар вершин называется ребром (также называемым ссылкой или линией ). ^[1] Обычно граф изображается в схематической форме в виде набора точек или кружков для вершин, соединенных линиями или кривыми для ребер.

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

Графы — основной предмет, изучаемый теорией графов. Слово «график» впервые было использовано в этом смысле Дж. Дж. Сильвестром в 1878 году из-за прямой связи между математикой и химической структурой (то, что он назвал химико-графическим изображением). ^[2]^[3]

Определения [ править ]

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

График [ править ]

Граф , (иногда называемый неориентированным графом чтобы отличить его от ориентированного графа , или простым графом , чтобы отличить его от мультиграфа ) ^[4]^[5] — пара $G = (V, E)$ , где $V$ — набор, элементы которого называются вершинами (единственное число: вершина), а $E$ — набор неупорядоченных пар. $\{v_{1},v_{2}\}$ вершин, элементы которых называются ребрами (иногда звеньями или линиями ).

Вершины $u$ и $v$ ребра ${u, v}$ ребра называются конечными точками . Говорят, что ребро соединяет $u$ и $v$ и инцидентно им . Вершина не может принадлежать ни одному ребру; в этом случае она не соединяется ни с одной другой вершиной и называется изолированной . Когда край $\{u,v\}$ существует, вершины $u$ и $v$ называются смежными .

Мультиграф — это обобщение , позволяющее нескольким ребрам иметь одну и ту же пару конечных точек. В некоторых текстах мультиграфы называют просто графами. ^[6]^[7]

Иногда графам разрешается содержать петли — ребра, соединяющие вершину с самой собой. Чтобы разрешить циклы, парам вершин в $E$ должно быть разрешено иметь один и тот же узел дважды. Такие обобщенные графы называются графами с петлями или просто графами , если из контекста ясно, что петли разрешены.

Обычно множество вершин $V$ считается конечным (что означает, что множество ребер $E$ также конечно). Иногда бесконечные графы рассматривают , но обычно их рассматривают как особый вид бинарных отношений , поскольку большинство результатов о конечных графах либо не распространяются на бесконечный случай, либо требуют совсем иного доказательства.

Пустой граф — это граф, имеющий пустое множество вершин (и, следовательно, пустое множество ребер). Порядок номер графа — это его $| В |$ вершин, обычно обозначаемых $n$ . Размер номер графа — это его $| Е |$ ребер, обычно обозначаемых $m$ . Однако в некоторых контекстах, например для выражения вычислительной сложности алгоритмов, термин « размер» используется для обозначения величины $| В | + | Е |$ (в противном случае непустой граф мог бы иметь размер 0). Степень валентность или вершины — это количество инцидентных ей ребер; для графов с циклами цикл учитывается дважды.

В графе порядка $n$ максимальная степень каждой вершины равна $n - 1$ (или $n + 1$ , если циклы разрешены, поскольку цикл вносит 2 в степень), а максимальное количество ребер равно $n (n - 1). /2$ (или $n (n + 1)/2,$ если циклы разрешены).

Ребра графа определяют симметричное отношение на вершинах, называемое отношением смежности . В частности, две вершины $x$ и $y$ являются смежными, если ${x, y}$ является ребром. Граф полностью определяется своей матрицей смежности $A$ , которая представляет собой $размера n \times n$ квадратную матрицу $, где A ij$ определяет количество соединений от вершины $i$ к вершине $j$ . Для простого графа $A ij$ равен либо 0, что указывает на разъединение, либо 1, что указывает на соединение; более того, $A ii = 0,$ поскольку ребро в простом графе не может начинаться и заканчиваться в одной и той же вершине. Графы с циклами будут характеризоваться тем, что некоторые или все $A ii$ равны положительному целому числу, а мультиграфы (с несколькими ребрами между вершинами) будут характеризоваться тем, что некоторые или все $A ij$ равны положительному целому числу. Неориентированные графы будут иметь симметричную матрицу смежности (что означает $A ij = A ji$ ).

Ориентированный граф [ править ]

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

или Ориентированный граф орграф — это граф, в котором ребра имеют ориентацию.

В одном ограниченном, но очень распространенном смысле этого термина: ^[8] — ориентированный граф это пара $G = (V, E)$ , содержащая:

$V$ — набор вершин узлами (также называемых или точками ) ;
$E$ — набор ребер , (также называемых направленными ребрами направленными связями , направленными линиями , стрелками или дугами ), которые представляют собой упорядоченные пары различных вершин: $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ .

Во избежание двусмысленности объект такого типа можно назвать именно ориентированным простым графом .

В ребре $(x, y)$ направленном от $x$ к $y$ , вершины $x$ и $y$ называются концами ребра, $x -$ хвостом ребра ребра и $y -$ головой , . Говорят, что x $и$ y $и$ инцидентно ребро x $соединяет$ и $y$ . Вершина может существовать в графе и не принадлежать ребру. Ребро $(y, x)$ называется перевернутым ребром $(x, y)$ . Множественные ребра , недопустимые согласно приведенному выше определению, представляют собой два или более ребра с одинаковым хвостом и одной и той же головкой.

В более общем смысле термина, допускающего наличие нескольких ребер, ^[8] ориентированный граф иногда определяется как упорядоченная тройка $G = (V, E, φ)$ , содержащая:

$V$ — набор вершин узлами (также называемых или точками ) ;
$E$ , набор ребер , (также называемых направленными ребрами направленными связями , направленными линиями , стрелками или дугами );
$φ$ , функция инцидентности , отображающая каждое ребро в упорядоченную пару вершин (т. е. ребро связано с двумя различными вершинами): $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ .

Во избежание двусмысленности объект такого типа можно назвать именно ориентированным мультиграфом .

Петля — это ребро , которое соединяет вершину с самой собой. Ориентированные графы, определенные в двух определениях выше, не могут иметь петель, потому что петля, соединяющая вершину $x$ самому себе является ребром (для ориентированного простого графа) или инцидентно (для ориентированного мультиграфа) $(x,x)$ которого нет в $\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}$ . Поэтому, чтобы разрешить циклы, определения должны быть расширены. Для ориентированных простых графов определение $E$ следует изменить на $E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}$ . Для ориентированных мультиграфов определение $\phi$ следует изменить на $\phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}$ . Чтобы избежать двусмысленности, эти типы объектов можно назвать именно направленным простым графом, допускающим циклы , и ориентированным мультиграфом, допускающим циклы (или колчаном ) соответственно.

Ребра ориентированного простого графа, допускающие петли $G,$ представляют собой однородное отношение С на вершинах графа $G$ называемое отношением смежности графа $G.$ , В частности, для каждого ребра $(x, y)$ его конечные точки $x$ и $y$ считаются смежными друг с другом, что обозначается $x ~ y$ .

Смешанный график [ править ]

Смешанный граф — это граф, в котором некоторые ребра могут быть направленными, а некоторые — ненаправленными. Это упорядоченная тройка $G = (V, E, A)$ для смешанного простого графа и $G = (V, E, A, φ E, φ A)$ для смешанного мультиграфа с $V$ , $E$ (неориентированные ребра), $A$ (направленные ребра), $φ E$ и $φ A$ , определенные выше. Ориентированные и неориентированные графы являются особыми случаями.

Взвешенный график [ править ]

граф Взвешенный или сеть ^[9]^[10] — это граф, в котором каждому ребру присвоен номер (вес). ^[11]Такие веса могут представлять, например, стоимость, длину или мощность, в зависимости от решаемой проблемы. Такие графы возникают во многих контекстах, например, в задачах о кратчайшем пути, таких как задача коммивояжера .

Типы графиков [ править ]

Ориентированный граф [ править ]

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

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

Обычный график [ править ]

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

Полный график [ править ]

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

Конечный граф [ править ]

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

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

Связный граф [ править ]

В неориентированном графе неупорядоченная пара вершин { x , y } называется связной , если путь ведет от x к y . В противном случае неупорядоченная пара называется несвязной .

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

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

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

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

Двудольный граф [ править ]

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

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

Граф пути [ править ]

Граф путей или линейный граф порядка n ≥ 2 — это граф, в котором вершины могут быть перечислены в порядке v ₁ , v ₂ , …, v _n так, что ребрами являются { v _i , v _{i +1} } , где i = 1, 2, …, n − 1. Графы путей можно охарактеризовать как связные графы, в которых степень всех вершин, кроме двух, равна 2, а степень двух оставшихся вершин равна 1. Если граф путей встречается как подграф другого графа, это путь в этом графе.

Планарный граф [ править ]

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

График цикла [ править ]

Граф циклов или круговой граф порядка n ≥ 3 — это граф, в котором вершины могут быть перечислены в порядке v ₁ , v ₂ , …, v _n так, что ребрами являются { v _i , v _{i +1} } , где я знак равно 1, 2, …, n - 1, плюс ребро { v _n , v ₁ } . Графы циклов можно охарактеризовать как связные графы, в которых степень всех вершин равна 2. Если граф циклов встречается как подграф другого графа, он является циклом или схемой в этом графе.

Дерево [ править ]

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

Лес путем, или, что то же самое , — это неориентированный граф, в котором любые две вершины соединены не более чем одним ациклический неориентированный граф или, что то же самое, непересекающееся объединение деревьев.

Политри [ править ]

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

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

Продвинутые классы [ править ]

Более продвинутые виды графиков:

граф Петерсена и его обобщения;
идеальные графики ;
кографы ;
хордальные графы ;
другие графы с большими группами автоморфизмов : вершинно-транзитивные , дуготранзитивные и дистанционно-транзитивные графы ;
сильно регулярные графы и их обобщения, дистанционно регулярные графы .

Свойства графиков [ править ]

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

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

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

Категория категория всех графов — это с запятой Set ↓ D, где D : Set → Set — это функтор, переводящий набор s в s × s .

Примеры [ править ]

Диаграмма представляет собой схематическое изображение графа с вершинами $V=\{1,2,3,4,5,6\}$ и края $E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}.$
В информатике ориентированные графы используются для представления знаний (например, концептуальный граф ), конечных автоматов и многих других дискретных структур.
Бинарное отношение R на множестве X определяет ориентированный граф. Элемент x из X является прямым предшественником элемента y из X тогда и только тогда, когда xRy .
Ориентированный граф может моделировать информационные сети, такие как Twitter , где один пользователь следует за другим. ^[12]^[13]
Особенно регулярные примеры ориентированных графов дают графы Кэли конечно порожденных групп, а также смежные графы Шрайера.
В теории категорий каждая маленькая категория имеет направленный мультиграф, вершины которого являются объектами категории, а ребра — стрелками категории. На языке теории категорий говорят, что существует забывчивый функтор из категории малых категорий в категорию колчанов .

Операции с графами [ править ]

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

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

Обобщения [ править ]

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

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

Каждый граф порождает матроид .

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

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

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

См. также [ править ]

Примечания [ править ]

^ Трюдо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, расширенное издание. Под ред.). Нью-Йорк: Паб Dover. п. 19. ISBN 978-0-486-67870-2 . Архивировано из оригинала 5 мая 2019 года . Проверено 8 августа 2012 г. Граф — это объект, состоящий из двух наборов, называемых набором вершин и набором ребер .
^
См.:
- Джей Джей Сильвестр (7 февраля 1878 г.) «Химия и алгебра» , архивировано 4 февраля 2023 г. в Wayback Machine Nature , 17 : 284. дои : 10.1038/017284a0 . Со страницы 284: «Таким образом, каждый инвариант и ковариант становится выражаемым графиком, точно идентичным диаграмме Кекуле или химикографу».
- Дж. Дж. Сильвестр (1878 г.) «О применении новой атомной теории к графическому представлению инвариантов и ковариантов бинарных квантов – с тремя приложениями» , архивировано 2023 г. в 4 февраля Американском журнале математики, чистой и Применено , 1 (1): 64–90. дои : 10.2307/2369436 . JSTOR 2369436 . Термин «график» впервые появляется в этой статье на странице 65.
^ Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов . ЦРК Пресс . п. 35 . ISBN 978-1-58488-090-5 . Архивировано из оригинала 4 февраля 2023 г. Проверено 16 февраля 2016 г.
^ Бендер и Уильямсон 2010 , с. 148.
^ См., например, Иянага и Кавада, 69 J , с. 234 или Биггс, с. 4.
^ Бендер и Уильямсон 2010 , с. 149.
^ Грэм и др., стр. 5.
^ Перейти обратно: ^а ^б Бендер и Уильямсон 2010 , с. 161.
^ Стрэнг, Гилберт (2005), Линейная алгебра и ее приложения (4-е изд.), Брукс Коул, ISBN 978-0-03-010567-8
^ Льюис, Джон (2013), Структуры программного обеспечения Java (4-е изд.), Пирсон, стр. 405, ISBN 978-0133250121
^ Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики (под ред. международного студента). Бостон: Паб PWS-KENT. Компания р. 463. ИСБН 978-0-53492-373-0 . — Взвешенный граф это граф, в котором присвоено число w ( e ), называемое его весом каждому ребру e .
^ Гранжан, Мартин (2016). «Анализ социальной сети Twitter: составление карты сообщества цифровых гуманитарных наук» . Cogent Искусства и Гуманитарные науки . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . Архивировано из оригинала 02 марта 2021 г. Проверено 16 сентября 2019 г.
↑ Панкадж Гупта, Ашиш Гоэл, Джимми Лин, Аниш Шарма, Донг Ван и Реза Босаг Заде WTF: Система «за кем следить» в Твиттере. Архивировано 12 июля 2019 г. в Wayback Machine , Материалы 22-й международной конференции по миру. Интернет . дои : 10.1145/2488388.2488433 .

Ссылки [ править ]

Балакришнан, В.К. (1997). Теория графов (1-е изд.). МакГроу-Хилл. ISBN 978-0-07-005489-9 .
Банг-Дженсен, Дж.; Гутин, Г. (2000). Орграфы: теория, алгоритмы и приложения . Спрингер.
Бендер, Эдвард А.; Уильямсон, С. Гилл (2010). Списки, решения и графики. С введением в вероятность .
Берже, Клод (1958). Теория графов и ее приложения (на французском языке). Париж: Дюнод.
Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Издательство Кембриджского университета. ISBN 978-0-521-45897-9 .
Боллобас, Бела (2002). Современная теория графов (1-е изд.). Спрингер. ISBN 978-0-387-98488-9 .
Дистель, Рейнхард (2005). Теория графов (3-е изд.). Берлин, Нью-Йорк: Springer Verlag. ISBN 978-3-540-26183-4 .
Грэм, РЛ; Гретшель, М.; Ловас, Л. (1995). Справочник по комбинаторике . МТИ Пресс. ISBN 978-0-262-07169-7 .
Гросс, Джонатан Л.; Йеллен, Джей (1998). Теория графов и ее приложения . ЦРК Пресс. ISBN 978-0-8493-3982-0 .
Гросс, Джонатан Л.; Йеллен, Джей (2003). Справочник по теории графов . КПР. ISBN 978-1-58488-090-5 .
Харари, Фрэнк (1995). Теория графов . Издательство Аддисон Уэсли. ISBN 978-0-201-41033-4 .
Иянага, Шок; Кавада, Юкиёси (1977). словарь Энциклопедический математический МТИ Пресс. ISBN 978-0-262-09016-2 .
Цвиллингер, Дэниел (2002). Стандартные математические таблицы и формулы CRC (31-е изд.). Чепмен и Холл/CRC. ISBN 978-1-58488-291-6 .

Дальнейшее чтение [ править ]

Трюдо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, расширенное издание. Под ред.). Нью-Йорк: Dover Publications . ISBN 978-0-486-67870-2 . Проверено 8 августа 2012 г.

Внешние ссылки [ править ]

Ресурсы библиотеки о
Граф (математика)

Ресурсы в вашей библиотеке

СМИ, связанные с графиком (дискретная математика) на Викискладе?
Вайсштейн, Эрик В. «График» . Математический мир .

[:0-1] Трюдо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, расширенное издание. Под ред.). Нью-Йорк: Паб Dover. п. 19. ISBN 978-0-486-67870-2 . Архивировано из оригинала 5 мая 2019 года . Проверено 8 августа 2012 г. Граф — это объект, состоящий из двух наборов, называемых набором вершин и набором ребер .

[2] См.:
Джей Джей Сильвестр (7 февраля 1878 г.) «Химия и алгебра» , архивировано 4 февраля 2023 г. в Wayback Machine Nature , 17 : 284. дои : 10.1038/017284a0 . Со страницы 284: «Таким образом, каждый инвариант и ковариант становится выражаемым графиком, точно идентичным диаграмме Кекуле или химикографу».

Дж. Дж. Сильвестр (1878 г.) «О применении новой атомной теории к графическому представлению инвариантов и ковариантов бинарных квантов – с тремя приложениями» , архивировано 2023 г. в 4 февраля Американском журнале математики, чистой и Применено , 1 (1): 64–90. дои : 10.2307/2369436 . JSTOR 2369436 . Термин «график» впервые появляется в этой статье на странице 65.

[3] Джей Джей Сильвестр (7 февраля 1878 г.) «Химия и алгебра» , архивировано 4 февраля 2023 г. в Wayback Machine Nature , 17 : 284. дои : 10.1038/017284a0 . Со страницы 284: «Таким образом, каждый инвариант и ковариант становится выражаемым графиком, точно идентичным диаграмме Кекуле или химикографу».

[4] Дж. Дж. Сильвестр (1878 г.) «О применении новой атомной теории к графическому представлению инвариантов и ковариантов бинарных квантов – с тремя приложениями» , архивировано 2023 г. в 4 февраля Американском журнале математики, чистой и Применено , 1 (1): 64–90. дои : 10.2307/2369436 . JSTOR 2369436 . Термин «график» впервые появляется в этой статье на странице 65.

[3] Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов . ЦРК Пресс . п. 35 . ISBN 978-1-58488-090-5 . Архивировано из оригинала 4 февраля 2023 г. Проверено 16 февраля 2016 г.

[FOOTNOTEBenderWilliamson2010148-4] Бендер и Уильямсон 2010 , с. 148.

[5] См., например, Иянага и Кавада, 69 J , с. 234 или Биггс, с. 4.

[FOOTNOTEBenderWilliamson2010149-6] Бендер и Уильямсон 2010 , с. 149.

[7] Грэм и др., стр. 5.

[FOOTNOTEBenderWilliamson2010161-8] Перейти обратно: ^а ^б Бендер и Уильямсон 2010 , с. 161.

[9] Стрэнг, Гилберт (2005), Линейная алгебра и ее приложения (4-е изд.), Брукс Коул, ISBN 978-0-03-010567-8

[10] Льюис, Джон (2013), Структуры программного обеспечения Java (4-е изд.), Пирсон, стр. 405, ISBN 978-0133250121

[11] Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики (под ред. международного студента). Бостон: Паб PWS-KENT. Компания р. 463. ИСБН 978-0-53492-373-0 . — Взвешенный граф это граф, в котором присвоено число w ( e ), называемое его весом каждому ребру e .

[snatwitter-12] Гранжан, Мартин (2016). «Анализ социальной сети Twitter: составление карты сообщества цифровых гуманитарных наук» . Cogent Искусства и Гуманитарные науки . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . Архивировано из оригинала 02 марта 2021 г. Проверено 16 сентября 2019 г.

[twitterwtf-13] Панкадж Гупта, Ашиш Гоэл, Джимми Лин, Аниш Шарма, Донг Ван и Реза Босаг Заде WTF: Система «за кем следить» в Твиттере. Архивировано 12 июля 2019 г. в Wayback Machine , Материалы 22-й международной конференции по миру. Интернет . дои : 10.1145/2488388.2488433 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]