Graphs and Networks Review

Comprehensive vocabulary flashcards covering the fundamental concepts of graph theory, including graph properties, paths, planar graphs, and optimization algorithms.

Graph

A diagram consisting of a set of points called vertices and lines called edges that represent connections between objects or locations.

Vertex

A point or node in a graph representing an entity or location.

Edge

A line or connection between two vertices in a graph.

Loop

An edge that connects a vertex to itself, contributing $2$ to the degree of that vertex.

Multiple edges

Two or more edges that connect the same pair of vertices.

Degree of a vertex

The number of edges attached to a vertex, denoted as $\text{deg}(V)$, where a loop is counted twice.

Sum of degrees theorm

A property stating that in any graph, the total sum of degrees across all vertices is equal to exactly twice the number of edges, expressed as $2 \times e$.

Connected graph

A graph in which a sequence of edges exists to link every vertex to every other vertex.

Bridge

An edge in a connected graph that, if removed, would cause the graph to become disconnected.

Isomorphic graphs

Graphs that are considered equivalent because they contain the same number of vertices and edges with identical connection patterns, regardless of how they are drawn.

Adjacency matrix

A square matrix representing a graph where the rows and columns correspond to vertices, and the entries indicate the number of edges connecting them.

Planar graph

A graph that can be drawn on a flat surface such that no edges cross or intersect except at the vertices.

Face

A region of space bounded by the edges of a planar graph, including the infinite region surrounding the graph.

Euler’s formula

A relationship for connected planar graphs where the number of vertices ($v$) plus the number of faces ($f$) is equal to the number of edges ($e$) plus two, written as $v + f = e + 2$.

Walk

A sequence of edges where each edge joins successive vertices, used to move from one point to another in a graph.

Trail

A type of walk that contains no repeated edges.

Path

A type of walk that contains no repeated edges and no repeated vertices.

Circuit

A closed trail that starts and ends at the same vertex and has no repeated edges.

Cycle

A closed path that starts and ends at the same vertex, with no repeated edges and no repeated vertices except for the first and last.

Eulerian trail

A trail that traverses every single edge in a graph exactly once; it exists if a connected graph has precisely zero or two vertices with an odd degree.

Eulerian circuit

A circuit that traverses every edge in a graph exactly once and starts and ends at the same vertex; it exists if all vertices in a connected graph have an even degree.

Hamiltonian path

A path that visits every vertex in a graph exactly once, without needing to use every edge.

Hamiltonian cycle

A cycle that visits every vertex in a graph exactly once and returns to the starting vertex.

Weighted graph

A graph where each edge is assigned a numerical value, or weight, representing data such as distance, cost, or time.

Network

A weighted graph where the edge weights represent physical quantities.

Shortest path problem

The task of finding the route between two vertices in a network that results in the minimum total weight.

Tree

A connected graph that contains no cycles, loops, or multiple edges; for a tree with $n$ vertices, there are exactly $n - 1$ edges.

Spanning tree

A subgraph that contains all the vertices of a connected graph and forms a tree.

Minimum spanning tree

The spanning tree of a weighted graph that has the lowest possible total edge weight.

Greedy algorithm

A problem-solving strategy that makes the choice that looks best at the current moment with the hope of finding a global optimum.

Prim’s algorithm

A greedy algorithm used to find the minimum spanning tree of a graph by selecting the lowest weight edge connected to the existing tree until all vertices are included.

Kruskal’s algorithm

A greedy algorithm used to find the minimum spanning tree by sorting all edges from lowest weight to highest and adding them sequentially as long as they do not form a cycle.

Dijkstra’s algorithm

A greedy algorithm used to identify the shortest path between two specific points in a network by assigning and updating values to vertices based on edge weights.