Graph Theory Terms - Discrete 2

Parallel edges

edges that connect the same vertices

Simple graph

graph with no loops or parallel edges

Null graph

graph with no vertices or edges

Trivial graph

graph with one vertex

Adjacent edges

edges that have the same end vertex

Adjacent vertices

vertices that are connected by the same edge

Pendant vertex

vertex with degree of 1

Pendant edge

edge with a pendant vertex attached to it

Isolated vertex

vertex with degree of 0

Handshaking Theorem

sum of degrees of all vertices = 2* total # of edges

Degree sequence

list of all vertices’ degrees in descending order

Maximum possible degree

number of vertices - 1

Valid degree sequence:

1. must sum to an even number

2. cannot contain degrees greater than the max possible degree

3. minimum degree value possible = number of vertices with the max possible degree

Complete graph (Kn)

• all vertices are connected to each other

• each vertex has a degree of n-1

Cycle graph (Cn)

• n number of vertices and edges

• vertices have a degree of 2

Wheel graph (Wn)

• Add one more vertex to a cycle graph and connect it to every vertex

Complementary Graph (G’)

• contains the same number of vertices as G

• contains edges where G doesn’t

• edges in G + edges in G’ = max possible # of edges

• overlapping G and G’ = Kn

Bipartite graph (Bm,n)

• all vertices can be split into 2 disjoin groups V1 and V2

• edges connect a vertex in V1 to a vertex in V2

• |V1| = m, |V2| = n

Complete bipartite graph (Km,n)

• bipartite graph with all possible edges

• degree of each vertex in V1 = n

• degree of each vertex in V2 = m

Subgraph

• G’ is a subgraph of G if each edge in G’ has the same vertices as it does in G

• A graph is a subgraph of itself

Walk

• finite sequence alternating between vertices and edges

• starts with the INITIAL VERTEX

• ends with the TERMINAL VERTEX

• length of a walk is the number of edges in between the initial and terminal vertex

Trail

walk with no repeated edges

Path

walk with no repeated edges or vertices, with the exception of the initial and terminal vertices

Circuit

path where the initial vertex = the terminal vertex (only repeats are the vertex that is both the initial and terminal vertex)

• circuit vs cycle: cycle can have repeats, circuit cannot

Connected graph

• a graph is connected if there is walk between every pair of vertices

• trivial graph is connected

CLOSED walk/path

• initial vertex is the same as the terminal vertex

• closed walk = CYCLE

• closed path = CIRCUIT

Cut vertex

vertex whose removal increases the number of connected components

Cut edge

edge whose removal increases the number of connected components

Euler walk

• Walk in which every edge is used exactly once

• A CONNECTED graph has a Euler walk the graph has exactly 2 vertices with an odd degree

Euler circuit

• CLOSED walk that uses every edge exactly once (initial and terminal vertices must be the same)

• A CONNECTED graph has a Euler circuit if all the graph’s vertices have an even degree

Euler graph

Graph with a Euler circuit

Hamiltonian path

a path that uses every vertex exactly once

Hamiltonian circuit

a circuit in a connected graph that includes every vertex exactly once

Hamiltonian graph

graph with a Hamiltonian circuit

Dirac’s theorem

A simple graph G has a Hamiltonian circuit if G has more 3+ vertices (n >= 3), such that the degree of every vertex >= n/2

Ore’s theorem

A simple graph G has a Hamiltonian circuit if G has 3+ vertices (n >= 3), such that deg(u) + deg(v) >= n for every pair of non-adjacent vertices u and v

Weighted graph

graphs with edges that are assigned numerical values

Tree

connected graph with no circuits

an undirected graph is a tree iff there is a unique simple path between any 2 of its vertices

Trivial tree

tree with one vertex

Forest

disconnected graph in which each connected component is circuit-less

Rooted tree

tree where one vertex is assigned to be the root. All other vertices and edges move away from the root

Vertex level

number of edges in the unique walk between that vertex and the root, root level = 0

(rooted) tree height

greatest vertex level within the tree

Children

children of vertex v are the adjacent vertices 1 level below

Parent

parent of vertex w is its adjacent vertex 1 level above

Internal vertices

vertices with children

Leaf

vertex without children

Siblings

distinct vertices with the same parent

Ancestor/descendant

if v lies on a unique path between w and the root, v is w’s ancestor and w is a descendant

M-ary tree

A rooted tree with each internal vertex having at most m children. An m-ary tree is FULL if each internal vertex has exactly m children.

Binary search tree

2-ary tree

move left = vertex that is less than its parent

move right = vertex that is greater than its parent

Decision Tree

• each internal vertex is a question or attribute

• each branch is an resulting outcome

• each leaf is a final decision

Empty graph

graph with vertices but no edges

Spanning tree

subgraph of G which is a tree containing every vertex of G. minimum spanning tree is a spanning tree with the smallest possible sum of edge weights (found using prims or kruskals algo)