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
Simple graph that contains exactly one edge bertween each pair of distinct vertices
Complete Graph
A vertex of degree 0
Isolated
Describe a loop
No of degree (undirected):
No of degree (directed):
Number of edge:
No of adjacency (undirected):
No of adjacency(directed):
No of degree (undirected): 2
No of degree (directed):1
Number of edge:1
No of adjacency (undirected):2
No of adjacency(directed):1
Not isolated
Same initial and terminal vertex
Degree one
Pendant
- Connected by a line in undirected
Adjacent or neighbors
Number of edges incident with it
Determined by counting the lines that touch it
Denoted vy deg(v)
Degree
Starting vertex in directed
Initial Vertex
End vertex in directed
Terminal Vertices
Describe the adjacency
U——>V
U is adjacent to V
V is adjacent to U
When the arrow is pointing at V
V is the terminal
In-DEGREE or deg^-(v)
The arrow is pointing away from v
V is the initial vertex
Out-degree or deg^+(v)
Two vertices joined by an edge
Adjacent Vertices
Two edges that intersects at a vertex
Adjacent edges
Vertex of odd degree
Odd vertex
Vertex of even degree
Even vertex
sequence of vertices such that each vertex is adjacent to the next. In a path, each edge can be traveled only once.
path
number of edges in that path
length of a path
A path that starts and ends at the same vertex
circuit
A graph is connected if any two vertices can be joined by a path. If this is not possible then the graph is disconnected.
connected
The connected parts of a disconnected graph are called ____.
components
It is an edge in a connected graph whose removal makes it disconnected
Bridge
path that travels through every edge of the graph (once and only once)
- Loop and parallels are not counted
Euler Path
circuit that travels through every edge of a graph
- Loop and parallels are not counted
Euler Circuit
