M4_Graph Flashcards
study of mathematical structures called graphs that are used to model pairwise relations between objects
graph theory
solved the Königsberg bridge in 1735
Leonhard Euler
Applications of Graph Theory (At least one)
Computer networks
Distinguish between two chemical compounds with the same molecular formula but different structures
Solve shortest path problems between cities
Scheduling exams and assign channels to television stations
Car navigation system
Handshaking theorem
2e=Summation of edges and summation of degrees then multiply the sum
TYPE OF GRAPH
Consists of V, a nonempty set of vertices, and E, a set of unordered pairs of distinct elements of V called edges
U–W
|_/
|/
V
Simple (undirected) graph
- Consists of set of vertices V, set of Edges E and a function f from E to {{u,v} | u, v, V, u is not equal to v}
- The edges e1 and e2 are called multiple or parallel edges if f(e1)=f(e2)
- V={u,v,w}
E= {e1, e2, e3}
U—-W
||__/
||_/
||/
V
Multigraph
- Set of vertices V and set of Edges E, that are ordered pair elements of V (directed edges)
- G(V,E)
- V={u, v, w}
E={(u,v), (v,w), (w,u)}
U–W
^__/
|_/
|/
_v
V
Directed Graph
- Graph with weights or costs assigned to its edges
Weighted Graph
- Consists of set of vertices V, set of Edges E and a function f from E to {{u,v}|u,v,V}
- The edges e1 and e2 are multiple edges if f(e1)=f(e2)
- V={u,v,w}
E={e1, e2, e3, e4}
U–W <]
^___/
||_/
||/
_vv
V
Directed Multigraph
- Consists of set of vertices V, set of Edges E and a function F from E to {{u,v}|u, v , I V}
- LOOPS ARE ALLOWED
- V={u,v,w}
E= {e1, e2, e3, e4}
U–W ]
||___/
||_/
||/
V
Pseudograph
SPECIAL GRAPH
- Of a Graph G (V,E) is a graph H=(W, F) where
W )_ V and F (_ E
Subgraph
- The union of two simple graphs G1=(V1, E1) and G2=(V2, E2) is the simple graph with vertex set V1 U V2 and edge set E1 U E2
The union of G1 nad G2 is denoted by G1 U G2
Union U
simple graph that contains exactly one edge between each pair of distinct vertices
Complete Graph
The___Cn, n>=3, consists of n vertices v1, v2, …, vn and edges {v1, v2}, {v2, v3}, …, {vn-1, vn}, {vn,v1}
cycle
- When we add an additional vertex to the cycle Cn, and connect this new vertex to each of the n vertices in Cn by adding new edges
Wheel
- Qn
- Graph that has vertices representing the 2^n bit strings of length n
- Two vertices are adjacent if and only of the bit strings that they represent differ in exactly one bit position
N-cube
- A simple graph is called this if its vertex set V can be partitioned into two disjoint nonempty set V1 and V2
- Such that every edge in the graph connects a vertex in V1 with a vertes in V2
Barpartite Graph
- K m.n
- The graph that has its vertex set partitioned into two subsets of m and n vertices
- Two vertices are connected If and only if they are in different subsets
Complete Barpartite Graph
