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
the simple graphs G1 = (V1, E1) and G2 = (V2, E2) are *** if there is a bijection (an one-to-one and onto function) f from V1 to V2 with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are adjacent in G2, for all a and b in V1
isomorphism
- represents the graph such that with the help of that matrix we can draw a graph. This matrix can be denoted as [AC] As in every matrix, there are also rows and columns in incidence matrix [AC].
- ROWS: Number of vertex or nodes
- COLUMN: number of edges or brances
Incidence Matrix
- a square matrix used to represent a finite graph
- Represents whether the paor of vertices are adjacent or not
- ROWS: vertices
- COLULMNS: vertices
Adjacency Matrix
a visual representation of edges and vertices
Graph
the line between two boundaries
Edge
a point where two or more lines meet
Vertex
