Shared Flashcard Set

Details

Graph Theory
Graph Theory
38
Mathematics
Graduate
12/09/2010

Additional Mathematics Flashcards

 


 

Cards

Term
Matching
Definition
a set of edges without common vertices
Term
Complete Matching
Definition
a matching M such that every vertex is incident with an edge of M
Term
Perfect Matching
Definition
a matching which matches all vertices of the graph
Term
Maximum Matching
Definition
a matching that contains the largest possible number of edges
Term
Maximal Matching
Definition
a matching that is not a proper subset of any other matching in a graph
Term
M-alternating Path
Definition
a path whose edges are alternately in a matching and not in the matching
Term
M-matched Vertex
Definition
a vertex is incident with one of the edges of the matching
Term
M-unmatched Vertex
Definition
a vertex is not incident with one of the edges of the matching
Term
M-augmented Path
Definition
an alternating path joining 2 M-unmatched vertices
Term
Distance in a graph
Definition
the number of edges in a shortest path connecting them
Term
Eccentricity of a Vertex
Definition
the greatest geodesic distance between 2 vertices
Term
Eccentric Vertex
Definition
a vertex whose distance between another vertex is the eccentricity
Term
Mutually Eccentric Vertices
Definition
2 vertices whose distance is the eccentricity of the graph
Term
Radius of a Graph
Definition
the minimum eccentricity of any vertex
Term
Center of a Graph
Definition
the set of all vertices of minimum eccentricity
Term
Diameter of a Graph
Definition
the maximum eccentricity of any vertex in the graph
Term
Periphery of a Graph
Definition
the set of vertices with max eccentricity
Term
Antipodal Vertices
Definition
2 vertices whose distance is the diameter of a graph
Term
Diametral Path
Definition
a geodesic joining a diametral pair of vertices
Term
Radial Path
Definition
a geodesic joining a central vertex to one of its eccentric vertices
Term
Geodesic
Definition
a path between 2 vertices of min length
Term
Cut Vertex
Definition
any vertex that when removed increases the number of connected components.
Term
Vertex Connectivity of a Graph
Definition
the min number of vertices whose deletion makes a graph disconnected or trival
Term
Edge Connectivity of a Graph
Definition
the min number of edges whose deletion makes a graph disconnected or trivial
Term
k-connected Graph
Definition
a graph whose vertex connectivity is equal or greater than k
Term
Block
Definition
a subgraph that has no cut vertex
Term
Block in a Graph
Definition
a maximal connected subgraph
Term
Eulerian Graph
Definition
a graph with an Eulerian circuit
Term
Eulerian Circuit
Definition
a trail in a graph which visits every edge exactly once and starts and ends on the same vertex
Term
Semi-eulerian Graph
Definition
a graph that has an Eulerian trail but not an Eulerian circuit
Term
Hamiltonian Cycle
Definition
a cycle in an symmetric graph which visits each vertex exactly once and also returns to the starting vertex
Term
Hamiltonian Graph
Definition
A graph that contains a Hamiltonian cycle
Term
Semi-Hamiltonian Graph
Definition
a graph that has a Hamiltonian path but no Hamiltonian cycle
Term
Berge's Matching Thm
Definition
a matching in a graph is max iff there is no M-augmenting path in the graph
Term
The Triangle Inequality
Definition
1. d(u,v)>=0 and d(u,v)=0 iff u=v
2. d(u,v)=d(v,u) for all u,v
3. d(u,v)<=d(u,w)+d(w,u) for all u,v,w
Term
Haray's Center Block Thm
Definition
The center of a connected graph belongs to a single block of the graph
Term
Characterization of Eulerian Graphs
Definition
a graph is eulerian iff the graph is connected and every vertex has an even degree
Term
Characterization of Semi-eulerian Graphs
Definition
a connected graph whose has exactly 2 vertices of odd degree, and an eulerain trail connects them
Supporting users have an ad free experience!