Final Discrete Structures Vocab

Graph

a collection of a non-empty set of vertices and edges

End Vertices

The two vertices on either end of an edge

Parallel Edges

Edges with the same start and end vertices

Loop

An edge where both of its end vertices are the same vertex.

Simple Graph

A graph without loops or edges

Empty Graph

A graph with no edges, but any amount of vertices N

Null Graph

A graph with no vertices

Trivial Graph

A graph with only one vertex

Adjacent Edges

Edges that share 1 or more vertices

Adjacent Vertices

vertices that are connected by the same edge. A vertex can be term to itself if a loop is involved

Degree

the total number of edges that have v as an end vertex. Count loops twice

Pendent Vertex

vertex with a degree of 1

Pendent Edge

An edge that is connected to a pendent vertex.

Isolated Vertex

a vertex with a degree of 0, no edges connecting to it

Degree Sequence

The degrees of all the vertices in a graph listed in decreasing order

graphic

if a degree sequence forms a simple graph

Subgraph

A graph formed from a subset of the vertices and edges of another graph.

Complete Graph

a graph where every vertex is adjacent to all the other vertices

Cycle Graph

A graph where n vertices, n is at least 3, and each vertex has a degree of two

Wheel Graph

A cycle graph but with an additional vertex that is adjacent to all the vertices of the cycle graph.

Bipartite Graph

A graph where its vertices can be divided into two disjoint sets, v1, and v2 where none of the vertices within a subset are adjacent to each other.

Complete Bipartite Graph

a bipartite graph where each edge in one set of vertices is adjacent to all the other edges in the other subset and vice versa

Walk

Allows repeating edges and vertices.

Trail

allows repeating vertices, but not repeating edges.

Path

No repeating vertices or edges.

Closed walk

A walk from initial → initial vertex.

Circuit

a closed trail

Cycle

a closed path

Euler Walk

a trail that uses all the edges in a graph

Euler Circuit

A closed trail that uses all the edges in a graph. This implies a Eulerian Graph.

Hamiltonian Cycle

A closed path using all vertices in a graph. Implies a Hamiltonian Graph and Path

Hamiltonian Path

A path using all the vertices in a graph.

tree

A connected graph with no circuits or cycles

Trivial Tree

A trivial graph or a tree with only one vertex.

Forest

A disconnected graph, with each component being a tree.

Rooted Tree

A graph with one vertex designed as the root, and every edge pointing away from the root.

Level

the number of edges from a vertex to the root on its unique path in a tree. term of the root is 0.

Height

The maximum level of a tree

Children

all the adjacent vertices below vertex v

Parent

The vertex that is adjacent to the current vertex and one level above the current vertex

Ancestors

all the vertices, excluding the current and the root, on the unique path to the root.

Descendants

All the vertices that are connected and higher level than the current vertex (below it).

Dirac

if every vertex, n at least 3, has a degree of at least n/2, that graph has Hamiltonian Cycle and is a Hamiltonian Graph

Ore

If G is a simple graph, n is at least 3, and any two non-adjacent vertices degrees sum up to at least n, G has a Hamiltonian circuit and is a simple graph.

M-ary tree

a tree where the internal vertices have at most m children

Full m-ary tree

a tree where the internal vertices have exactly m children.

Balanced m-ary tree

when the leaf nodes are at level h or h-1.

Decision tree

a tree where each internal node represents a decision

Spanning tree

A subgraph of G, that is a tree, which contains every vertex of G.

Weighted Graph

A graph where we assign weights to each of the edges.

Minimum Spanning Tree

A spanning tree with the smallest possible sum of weights of its edges.