Graph Theory Exam 1

Graph Theory Exam 1 Study Set Designed for HNR-1301 Quan. Rea: Graph Theory/Sci Net Dr. Fuselier

Network

A collection of points joined together in pairs by lines

Nodes/Vertices

The points on a graph

Links/Edges

The lines on a graph

Mathematical Model

A mathematical object we can study and assess and see how it affects the underlying scenario

Graph

A collection of vertices joined by edges

Size/Order

Number of vertices, often denoted as "N", on a graph

Degree

Number of edges a vertex has connected with other vertices

Density

Ratio of number of edges in the network to the total possible number of edges; (\# of edges)/((n-(n-1))/2)

Typical Notation

G \= (V,E)

Set

Collection, group of, some number of

Set Notation

{s}, where "s" is the set objects

Directed Graph

A graph with edges that have a direction associated with them, denoted by an arrow

Undirected Graph

A graph with edges that do not have a direction associated with them

Cycle

Begins and ends at same vertex, no vertex is repeated, length \= number of edges

Tree

Contains no cycles, every pair of vertices has a path connecting them, unique route between 2 vertices, if disconnected it is no longer a tree

Complete

Every pair of vertices is joined by an edge, every vertex has the same degree, also called cliques

Isolated

A vertex with 0 degrees

Bipartite

Vertex set can be divided into two nonoverlapping sets U and V, such that every edge in the graph connects a U-vertex with a V-vertex

Geodesic Path

Path of shortest length between 2 vertices

Diameter

Largest, most efficient distance between any pair of vertices which can be connected in the graph

Reciprocity

An edge from A to B is reciprocated if there is also an edge from B to A (only for directed graphs)

Vertex Connectivity

Minimum number of vertices whose deletion disconnects the graph (Κ(G))

Edge Connectivity

Minimum number of edges whose deletion disconnects the graph (λ(G))

Bridge

Edge that if lost/removed will disconnect the graph

Length

Distance between 2 vertices

Path

Sequence of vertices beginning at U, traveling along edges in the graph, and ending at V