Shared Flashcard Set

Details

Graph Theory Defs
Virginia Tech 5454
69
Mathematics
Graduate
02/21/2009

Additional Mathematics Flashcards

 


 

Cards

Term
clique
Definition
set of pairwise adjacent vertices
Term
path
Definition

simple graph whose vertices can be ordered so that two vertices are adjacent iff they are consecutive in the list

 

A walk that has no repeated vertices or edges

Term
cycle
Definition
a graph with an equal number of vertices and edges whose vertices can be placed around a circle so that two vertices are adjacent iff they appear consecutively along the circle
Term
adjacency matrix
Definition
For a graph with n vertices, the adjacency matrix is an n x n matrix where element (i,j) is the number of edges in G with endpoints {vi, vj}
Term
incidence matrix
Definition
For a graph with n vetices and m edges, the incidence matrix is an n x m matrix where each element (i,j) is 1 if vi is an endpoint of ej, otherwise 0.
Term
A(G)
Definition
Symbol for adjacency matrix
Term
M(G)
Definition
Symbol for incidence matrix
Term
Girth
Definition
Length of the shortest cycle of a graph
Term
automorphism
Definition
an isomorphism that maps G to G.
Term
vertex-transitive graph
Definition
a graph that for every pair u,v in V(G) there is an automorphism that maps u to v.
Term
trail
Definition
a walk with no repeated edges
Term
component
Definition
maximally conneted subgraph
Term
induced subgraph
Definition
subgraph obtained by removing a vertex/vertices
Term
Eulerian Graph
Definition
A graph that has a closed trail containing all edges
Term
Eulerian Circuit/Trail
Definition
A circuit/trail that contains all edges
Term
Even/Odd Graph
Definition
Graph whose vertices are all of even/odd degree.
Term
neighborhood
Definition
set of vertices adjacent to a given vertex
Term
N(v)
Definition
symbol for neighborhood of vertex v
Term
order of a graph
Definition
number of vertices in a graph
Term
n(G)
Definition
symbol for the order of a graph
Term
size of a graph
Definition
number of edges in a graph
Term
e(G)
Definition
symbol for size of a graph
Term
G + H
Definition
disjoint union of G and H
Term
mG
Definition
graph consisting of m pairwaise disjoint copies of G
Term
A graph G is H-free if
Definition
G has no induced subgraph isomorphic to H
Term
2-switch
Definition
replacement of a pair of edges xy and zw in a simple graph by the edges yz and wx given that yz and wx did not appear in the graph originally
Term
distance from vertices u and v
Definition
least length of a u,v path
Term
d(u,v)
Definition
symbol for the distance from u to v
Term
diameter (diam G)
Definition
length of the longest u,v path for all u,v
Term
eccentricity of vertex u
Definition
length of the path from u to the farthest vertex.
Term
radius of G
Definition
the eccentricity of the vertex with the smallest eccentricity.
Term
center of a graph
Definition
subgraph induced by the vertices of minimum eccentricity.
Term
matching
Definition
set of non-loop edges with no shared endpoints
Term
saturated vertices
Definition
vertices incident to the edges of a matching
Term
unsaturated vertices
Definition
vertices that are not incident to the edges of a matching
Term
perfect matching
Definition
a matching that saturates every vertex
Term
M-alternating path
Definition
path that alternates between edges in M and edges not in M
Term
M-augmenting path
Definition
M-alternating path whose endpoints are unsaturated
Term
vertex cover
Definition
set of vertices that contains at least one endpoint of every edge
Term
independence number
Definition
maximum size of independent set of vertices
Term
edge cover
Definition
set of edges L such that every vertex is incident to some edge of L.
Term
α(G)
Definition
symbol for independence number
Term
α'(G)
Definition
symbol for maximum size of matching
Term
β(G)
Definition
symbol for minimum size of vertex cover
Term
β'(G)
Definition
symbol for minimum size of edge cover
Term
k-factor
Definition
k-regular spanning subgraph of a graph
Term
o(H)
Definition
symbol for the number of odd components in H
Term
join
Definition
graph obtained from the disjoint union of two graphs, adding every possible edge between them
Term
G v H
Definition
symbol for the join of G and H
Term
vertex cut
Definition
a set S of vertices such that G - S has more than one component
Term
connectivity
Definition
minimum size of a vertex cut such that G - S is disconnected or has only one vertex
Term
κ(G)
Definition
symbol for the connectivity of a graph G
Term
edge cut
Definition
set of edges F such that G - F has more than one component
Term
edge-connectivity
Definition
minimum size of an edge cut
Term
κ'(G)
Definition
symbol for edge connectivity of G
Term
[S, S']
Definition
symbol for an edge cut where the cut is all edges between the sets of vertices S and S'
Term
bond
Definition
minimal nonempty edge cut
Term
internally disjoint paths
Definition
paths from u to v that share no common internal vertex.
Term
subdivision of an edge
Definition
adding a vertex between the two endpoints of the edge
Term
λ(x,y)
Definition
maximum size of a set of pairwise internally disjoint x,y-paths
Term
val(f) of a flow f
Definition
net flow into the sink
Term
flow
Definition
assigns a value f(e) to each edge e
Term
feasible flow
Definition
For every edge e, f(e) <= c(e) and the net flow of every vertex other than the source and sink is 0.
Term
network
Definition
a digraph with a nonnegative capacity c(e) assigned to every edge e and a distinguished souce vertex s and sink vertex t
Term
f-augmenting path
Definition
source to sink path P such that for each e in E(P), if P follows e in the forward direction then f(e) < c(e). If P follows e in the backward direction then f(e) > 0.
Term
tolerance
Definition

tolerance of a source to sink path P is equal to the min(ε(e)) where ε(e) equals:

 

ε(e)=c(e) - f(e) when e is forward on P

ε(e)=f(e) when e is backward on P

Term
source/sink cut
Definition

consists of edges from a source set S to a sink set T where S and T partition the nodes with s in S and t in T.

 

The capacity of a cut cap(S,T) is the total of the capacities on the edges of S and T

Term
[S,T]
Definition
symbol for a souce sink cut
Supporting users have an ad free experience!