hascycles

Определите, содержит ли график циклы

Синтаксис

tf = hascycles(G)

Описание

tf = hascycles(G) возвращает логический 1 TRUE) если график G содержит один или несколько циклов и логического 0 ложь) в противном случае.

Примеры

свернуть все

Определите, имеет ли неориентированный граф циклы

Попробовать в MATLAB

Создайте и постройте неориентированного графа.

G = graph([1 1 1 1],[2 3 4 5]);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Определите, имеет ли график циклы.

tf = hascycles(G)

tf = logical
   0

Теперь добавьте ребро в график между узлом 2 и узлом 3. Повторно постройте график.

G = addedge(G,2,3);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Определите, имеет ли новый график циклы.

tf2 = hascycles(G)

tf2 = logical
   1

Определите, имеет ли ориентированный граф циклы

Попробовать в MATLAB

Исследуйте различие между hascycles и isdag функции, работающие с ориентированным графом.

Создайте и постройте ориентированного графа.

s = [1 1 1 2 3 3 3 4 6];
t = [2 4 5 5 6 7 4 1 4];
G = digraph(s,t);
plot(G)

Figure contains an axes. The axes contains an object of type graphplot.

Определите, содержит ли график какие-либо циклы.

tf = hascycles(G)

tf = logical
   1

hascycles возвращает true когда ориентированный граф содержит цикл.

Теперь используйте isdag определить, направлен ли график и нециклический.

tf2 = isdag(G)

tf2 = logical
   0

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

Входные параметры

свернуть все

`G` — Введите график
`graph` возразите | `digraph` объект

Введите график в виде любого graph или digraph объект. Используйте graph создать неориентированного графа или digraph создать ориентированного графа.

Пример: G = graph(1,2)

Пример: G = digraph([1 2],[2 3])

Больше о

свернуть все

Циклы графика

Цикл существует в графике, когда существует непустой путь, в котором только повторяются первые и последние узлы. Пример цикла: (Node1 - Node2 - Node3 - Node1).

Цикл не может пересечь то же ребро дважды. Например, цикл (Node1 - Node2 - Node1) в неориентированном графе только существует, если существует больше чем одно ребро, соединяющее Node1 и Node2. По этому определению самоциклы рассчитывают как циклы, хотя они не могут быть частью никаких больших циклов.