Graph Terms

Graph

Consists of vertices connected by edges

Network

Has a weight associated with each edge

Vertex

Point on a graph

What are vertices also called

Nodes

Edge

Line segment joining two vertices

What are edges also called

Arcs

What are networks also called

Weighted graphs

Vertex set

The list of vertices

Edge set

The list of edges

Subgraph of graph G

A graph each of whose vertices belong to G, and each of whose edges belong to G

Degree of a vertex

The number of edges incident to it

What is the degree of a vertex also known as

The valency/order of a vertex

Odd vertex

Has an odd degree

Even vertex

Has an even degree

Walk

A route along a graph from one vertex to the next

Path

A finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex vertex of the next, and in which no vertex appears more than once

Cycle

Closed path

What does it mean that a cycle is a closed path

The end vertex of the last edge is the start vertex of the first edge

Trail

A walk in which no edge is visited more than once

Hamiltonian cycle

A cycle that passes through every vertex of a graph once and only once and returns to its start vertex

When are vertices called connected vertices

If there is a path between them

When are graphs called connected graphs

All of its vertices are connected

Loop

An edge that starts and finishes at the same vertex

Simple graph

No loops and at most one edge connecting any pair of vertices

Directed edges

The edges have a direction associated with them

Digraph

A graph of directed edges

What is a digraph also known as

Directed graph

Euler’s handshaking lemma

The sum of the degrees of a vertex is equal to 2x the number of edges

Tree

A connected graph with no cycles

Spanning tree of a graph G

A subgraph which includes all vertices of G and is also a tree

Complete graph

Every vertex is directly connected by a single edge to each of the other vertices

Isomorphic graphs

Graphs with the same number of vertices and degrees of corresponding vertices are the same

What does K_n mean

A complete graph with n vertices

Adjacency Matrix

Each entry describes the number of arcs joining the corresponding vertices

Distance Matrix

Each entry describes the weight of the arcs joining the corresponding vertices