ATMAA — network vocabulary

network

a set of vertices connected by a set of edges which make up separated areas known as faces or regions

graph

another word for a network is…

loop

an edge that starts and ends at the same vertex

multiple edges

two edges which connect the same two vertices (if directed, must be going in the same direction)

adjacent vertices

two vertices which are connected by an edge(s)

weighted graph

a graph which has amounts, distances, or some other similar information affixed to each edge

directed edge

an edge that can be travelled only in a specific direction

arc

another word for a directed edge is…

digraph

a graph with directed edges

directed graph

another word for a digraph is…

undirected graph

a graph which includes no directed edges

simple graph

an unweighted, undirected graph with no loops or multiple edges

simple digraph

a directed graph with no loops or multiple edges

simple weighted graph

a weighted graph with no loops or multiple edges

walk

a sequence of vertices adjacent by edges

closed walk

a walk which begins and ends at the same vertex

open walk

a walk which begins and ends at different vertices

path

a walk with no repeat use of edges nor vertices

cycle

a walk with no repeat use of edges nor vertices aside from the first vertex, which it both begins and ends at / a path which begins and ends at the same vertex

closed path

another word for a cycle is…

length

the number of edges travelled in a walk including any repeats OR the total weight travelled in a walk of a weighted graph

trail

a walk which does not include any repeated edges

connected vertices

two vertices in an undirected graph between which there exists a path

connected graph

an undirected graph for which all vertices are connected

disconnected graph

an undirected graph for which all vertices are connected

bridge

any edge in a connected graph which, if removed, would turn the graph into a disconnected graph

complete graph

a simple graph in which every vertex is connected by every other vertex by a single each

subgraph

a graph that is a part of another larger graph

bipartite graph

a graph whose vertices can be split into two distinct groups so that each edge connects each vertex from one group with a vertex from the other

planar graph

a graph for which all edges are “in the same plan”, and as such can be drawn without any overlapping edges

euler’s rule

for any connected planar network, vertices + faces = edges + 2

tree

any connected simple graph which contains no cycles

degree

the number of edges which meet at a vertex

order

another word for degree is…

odd vertex

a vertex which has an odd number as its degree

even vertex

a vertex which has an even number as its degree

in-degree

the number of edges travelling in to meet a vertex in a directed graph

out-degree

the number of edges travelling out from a vertex in a directed graph

eulerian graph

a graph with zero odd vertices, thus containing an eulerian circuit

semi-eulerian graph

a graph with exactly two odd vertices, one at which the eulerian trail must start, and the other at which it must end

eulerian trail

a trail in a connected graph that traces every edge and only once each, repeated vertices permitted

eulerian circuit

a closed eulerian trail

hamiltonian path

a path which visits every vertex in a graph and only once each

hamiltonian cycle

a path which visits every vertex in a graph and only once each with the exception of the vertex at which it starts and must also end / a closed hamiltonian path

hamiltonian graph

a graph which contains a hamiltonian cycle

semi-hamiltonian graph

a graph which contains an open hamiltonian path

adjacency matrix

a matrix which describes the adjacency of pairs of vertices