Please enable JavaScript.
Coggle requires JavaScript to display documents.
10.5 GRAPH THEORY - Coggle Diagram
10.5 GRAPH THEORY
Subsets
Cliques
- subset of a directed graph that satisfies three conditions
First condition:
- the subset contains at least three vertices
Second condition:
- for each pair of vertices Pi and Pj in the subset,
both Pi ---> Pj and Pj ---> Pi are true
Third condition:
- the subset is as large as possible
(it is not possible to add another vertex to it
while satisfying the condition)
Ordered pairs
- also called directed edges
- (Pi, Pj)
- the notation Pi ---> Pj
indicates that the directed edge (Pi, Pj)
belongs to the directed graph
Vertex matrices
- nxn matrix M of a directed graph
- its elements are defined by mij = 1
if Pi ---> Pj and mij= 0 otherwise
Dominance directed graphs
Power of a vertex
- total number of 1-step and 2-step connections from it to other vertices
- A = M + M^2
Connections
- in any dominance directed graph, there is at least one vertex from which there is a 1-step or 2-step connection to any other vertex
Eg: P1, P2, P3 are elements of
the set {P1, P2, P3}
-