Graphs. 2nd half of the semester

Length of the path

Length of the path is amount of its edges.

Distance between two vertices

Distance between two vertices is the length of the shortest path connecting these vertices.

Distance function as metric

Finding distance: distance matrix

Find shortest path: BFS algorithm

Eccentricity

Diameter

Center of the graph

Radius of graph

relation between radius and diameter of graph. Theorem

Cycle

A cycle is the path that starts and ends and the same vertex with no repeated edges and vertices (except the start and the end).

Independent set of cycles

A set of cycles is independent if no cycle can be expressed as a combination of others.

Independency check for the set of cycles

Cyclomatic number of the graph

Edge graph

Theorem about number of edges and vertices of Edge Graph

Stability set

stability number

Greedy algorithm of Stable Set search

Clique

Clique is set of pairwise adjacent vertices

Key idea of clique

Finding a maximal stable set in G is equivalent to finding a clique in compliment of G

Dominating set

dominating number of graph G