path: root / Seminar11

Граф е наредена двойка G = (V, E), където V e непразно множество, чиито елементи се наричат върхове. Множеството E е крайно множество от ребра. Ребро наричаме двуелементно множество {v1, v2}, където v1 и v2 са елементи на V.
Припомняне:
Когато имаме двуелементно множество {v1, v2} е вярно, че {v1, v2} = {v2, v1}. При наредените двойки това не е вярно. За v1 != v2 имаме (v1, v2) != (v2, v1).
Наредената двойка (a, b) e множеството {{a}, {a, b}}. Да твърдим, че (a, b) = (b, a) e същото като да твърдим, че {{a}, {a, b}} = {{b}, {a, b}}. Това става единствено когато a = b.
{
    {0, 1, 1},
    {1, 0, 1},
    {1, 1, 0}
}
matrix[5][7] = true
matrix[7][5] = false
0: 1 -> 2
1: 0 -> 2
2: 1 -> 2
BFS(G = (V, E), s начален връх):
    foreach v in V:
        color[v] = white
        dist[v] = 0
        parent[v] = Nil
    color[s] = gray
    q = create_queue()
    q.push(s)

    while !q.empty():
        x = q.top()
        q.pop()

        foreach v in adjacent(x):
            if color[v] == white:
                color[v] = gray
                dist[v] = dist[x] + 1
                parent[v] = x
                q.push(y)
        color[x] = black
time = 0

DFS(G = (V, E)):
    foreach v in V:
        color[v] = while
        parent[v] = Nil

    foreach v in V:
        if color[v] == white:
            DFS-VISIT(G, i)

DFS-VISIT(G = (V, E), x):
    color[x] = gray
    discovered[x] = ++time
    foreach y in adj[x]:
        if color[y] == white:
            parent[y] = x
            DFS-VISIT(G, y)

    color[x] = black
    finalized[x] = ++time
Name	Size
..
README.md	21.4 KiB	log stats plain blame
find-cycle.cpp	1016 B	log stats plain blame
media	443 B	log stats plain
Понятие	Дефиниция
Примка в граф	Ребро от типа {v, v}
Път в граф	Редица от върхове (v_1, v_2, ..., v_n) за които е в сила {v_i, v_{i+1}} е елемент на E.
Цикъл в граф	Път p за който v_1 = v_n се нарича цикъл.
Прост път	Път p e прост ако всички елементи в редицата са уникални.
Дължина на път	Дължината на пътя е броя на ребрата в него.
Ацикличен граф	Граф, в който няма цикъл. Ако в графът има цикъл то той се нарича цикличен.
Свързан граф	Граф е свързан ако за всеки два върха u, v има път между u и v.
Силно свързани върхове	В ориентиран граф казваме, че върхове u, v са силно свързани ако съществува път от u до v и от v до u
Силно свързан граф	Силно свързан граф е ориентиран граф, за който всеки два върха са силно свързани.
Операция	Сложност
addVertex	O(n)
removeVertex	O(n)
addEdge	O(1)
removeEdge	O(1)
getSuccessors	O(n)
getPredecessors	O(n)