CSCE411 Exam 2 - Graph Notation and Terminology

Adjacent

Given (i,j), it is said that vertices i and j are adjacent.

Neighborhood

The neighborhood of a node is the set of nodes adjacent to it.

N(v) = { i ∈ V | (i,v) ∈ E }

Degree

The number of neighbors (adjacent nodes) a vertex has.

Generalized Graph Classes

Weighted, Directed

Weighted Graphs

Every edge (i,j) ∈ E is associated with a weight w_ij

Directed Graphs

All edges have a direction such that (i,j) means i → j

Does not necessarily imply that (i,j) = (j,i)

Basic Graph Types

Basic graph types include complete graphs, bipartite graphs, and triangles.

Complete Graph

Every pair of vertices is connected by an edge.

Bipartite Graph

All vertices can be separated into two groups. Edges only cross between gaps. No two vertices in a group share an edge.

Triangle

A set of three nodes that all share edges.

Edge Structures

Three common kinds of edge structures are edges, matchings, and connected components.

Path

A sequence of edges joining a sequence of vertices.

Matching

A set of edges without common vertices.

Connected Component

A maximal subgraph in which there is a path between every pair of nodes in the subgraph.

Common Graph Optimization Problems

Shortest path, maximum bipartite matching, finding connected components.

Graph Representation

The two means of representing a graph are either through an adjacency list or an adjacency matrix.

Adjacency List

The set of nodes such that each element in the adjacency list contains a list of adjacent nodes.

Adjacency Matrix

A matrix where each row/column represents the i-th/j-th vertex. An entry is either a 0 for no edge, or a 1 for an edge. Adj[2][3] indicates that there is an edge from 2 → 3.