Определите, содержит ли график циклы
Создайте и постройте неориентированного графа.
G = graph([1 1 1 1],[2 3 4 5]); plot(G)
Определите, имеет ли график циклы.
tf = hascycles(G)
tf = logical
0
Теперь добавьте ребро в график между узлом 2 и узлом 3. Повторно постройте график.
G = addedge(G,2,3); plot(G)
Определите, имеет ли новый график циклы.
tf2 = hascycles(G)
tf2 = logical
1
Исследуйте различие между 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)
Определите, содержит ли график какие-либо циклы.
tf = hascycles(G)
tf = logical
1
hascycles возвращает true когда ориентированный граф содержит цикл.
Теперь используйте isdag определить, направлен ли график и нециклический.
tf2 = isdag(G)
tf2 = logical
0
isdag возвращает false потому что график содержит цикл. В общем случае hascycles и isdag функции возвращают противоположные результаты для ориентированных графов.
allcycles | cyclebasis | isdag