Graph Theoey Flashcards
Basic definitions
Simple graph
A finite, non-empty set V(G) of elements called vertices, together with a possibly empty set E(G) of 2-element subsets of V(G), called edges where uv denotes the egde between a vertex u eV(G) and vertex v eV(G)
Order
Number of vertices, p
Size
Number of edges, q
Density
Relationship between number of edges and number of possible edges
q(G) /(p(G)c2)
Multigraph
More than 1 edge between vertices
Pseudograph
Contains a loop
Open neighbourhood
All vertices surrounding a vertex Ng(v)
Closed Neighbourhood
All vertices surrounding the vertex and the vertex itself Ng[V]
Incident
Edge and vertex are touching
Degree
DegG(Vi) number of vertices adjacent to vertex i
Isolated vertex
Degree 0
End vertex
Degree 1
Even vertex
Even degree, include isolated vertices
Minimum degree
Lowest degree of a vertex small delta
Maximum degree
Maximum degree of a vertex big delta
Fundamental thm of graph theory (thm 2.1)
S(from 1 to p) deg(vi) =2q
Corollary of 2.1
Every graph has an even number of odd vertices
Subgraph
V(H) is a subset of V(G) and E(H) is a sunset of E(G)
Propper subgraph
Can’t be exactly the same
Spanning subgraph
Vertices exactly the same, but not all edges
are there
Edge induced subgraph
G non empty subset T is a subset of E(G) and vertex set V()
(no isolated vertices)
Walk
Finite alternating sequence of vertices and edges from v1 to vn
Path
A walk with no repeated vertices (therefore no repeated edges)
Distance
dG1(vi, vj) shortest path between the two vertices
Cycle
Path where you end where you started
Acyclic graph
Graph with no cycles
Trail
No repeates edges (vertices don’t matter)
Circuit
Trail that closes
Connected graph
There is a path between every vertex in the graph
Disconnected graph
There are at least 2 vertices in the graph where there is no path between them
Component
“seperate bits”
Bridge
Edge which, if removed will increase the number of components of the graph
Cut vertex
Vertex which, if removed, increases the number of components
R-regular
All vertices have degree r
Complete graph of order n
Has all possible edges:
(n-1) regular
(nc2) edges
Partite set
No edges between vertices in set
Complete multipartite graph
Complete graph within partite sets
Planar graph
Graph that can be drawn with no edges crossing
Plane graph
Graph that is drawn with no edges crossing
Kuratowski’s thm
Graph is planar iff it doesn’t contain K5 or K3, 3
Nonplanar graph
Can’t be drawn without edges crossing
Tree
Acyclic connected graph, order n implies size n-1
Spanning tree
(a subgraph) tree ensuring a path between any 2 vertices
Adjacency matrix
Represents graph: 1 for edge 0 for no edge
Use capital letter: A(G2) =…
Directed graph
Finite, nonempty set V(D) of elements called vertices, together with a possibly empty set E(D) of ORDERED pairs of distinct vertices of D, called arcs where (u, v) denotes the arc from a vertex u to a vertex v element of V(D)
Out-neighbourhood
ND+ - open neighbourhood of all vertices adjacent FROM starting vertex
In neighbourhood
Open neighbourhood of all vertices adjacent TO starting vertex
ND-(V)
Out degree
Cardibality of out neighbourhood of vertex
In degree
Cardinality of in neighbourhood of vertex
Degree of vertex in directed graph
degD(v) = odD(v) + idD(v)
out degree of D(v) + in degree of D(v)
Ist theorem of digraph
Sum of all out degrees = sum of in degrees = q
Directed walk
Finite alternating sequence of vertices and arcs from v1 to vn (and the arcs in between them)
Semi walk
Finite alternating sequence of vertices and arcs (can travel in any direction on arcs)
Strongly connected
For all vertex pairs, there exists a path from 1 vertext to the other and visa versa (every vertex has an in degree of at least 1}
Weakly connected
For every vertexr pair, there is at least 1 path between them (the underlying graph is connected)
Disconnected graph
Different components
R-regular digraph
Out degree = in degree, for every vertex in the graph
Symmetric
Arc in 1 direction implies arc in the other direction
Asymmetric
Between each vertex there is only one arc (1 direction between each arc)
Tournament
Every pair of vertices in an asymmetric digraph are joined by exactly one arc
Directed tree
Asymmetric digraph whose underlying graph is a tree
Directed rooted tree
Exactly 1 vertex r, root of T, such that there exists a r-v path in T for every vertex of T
Size of a k(mxn) graph
(mnC2)-m(nC2)
Path length
Sum of weights of the edges travelled
Distance
Minimum sum of weights between 2 vertices
Origin/source
Where you start
Endpoint / destination
Where you end
