Network terminology

definitions

Vertices/Nodes

Points on a network/graph

Faces/Regions

The areas bounded by edges in a graph or network, representing distinct regions within the structure.

Edges

The lines connecting vertices/nodes in a graph or network, representing relationships or connections between them.

Arcs

Edges in a directed graph that connect vertices, representing relationships or pathways.

Multipleedges

Edges that connect the same pair of vertices in a graph

Traversable

A graph is traversable if it is possible to draw it without lifting the pen from the paper and without retracing any edges, meaning that all edges can be visited exactly once.

Loop

An edge in a graph that connects a vertex to itself, representing a relationship or pathway that starts and ends at the same vertex.

Weightedgraph

A graph in which each edge has an associated numerical value or weight, typically representing costs, lengths, or capacities.

Undirectedgraph

A graph where the edges have no direction, meaning that the connection between vertices is bidirectional and can be traversed in either direction.

Directedgraph

A graph in which the edges have a specific direction, indicating one-way relationships between vertices that cannot be traversed in reverse.

Simplegraph

A graph that does not have multiple edges between the same pair of vertices and does not have loops, meaning that each edge connects two different vertices.

Openwalk

A walk in a graph that does not require returning to the starting vertex and can include repeated edges and vertices.

closedwalk

A walk in a graph that starts and ends at the same vertex. It may include repeated edges and vertices but must return to the origin.

openpath

A path in a graph that does not repeat any vertices. It starts and ends at different vertices, and all edges are distinct.

closedpath/cycle

A cycle in a graph that starts and ends at the same vertex without repeating any vertices. It includes distinct edges, forming a closed loop.

trail

A walk in a graph that does not repeat any edges but may revisit vertices. It connects a sequence of vertices in a way that maintains distinct edges.

closedtrail

A walk in a graph that starts and ends at the same vertex without repeating any edges. It can revisit vertices but must use distinct edges.

connected

A property of a graph where there is a path between every pair of vertices, ensuring that the graph is a single component without any isolated vertices.

completegraph

A graph in which every pair of distinct vertices is connected by a unique edge. In a complete graph, all possible edges are present, making it maximally connected.

Bridge

An edge in a graph whose removal increases the number of connected components, thereby disconnecting the graph.

Planargraph

A graph that can be drawn on a plane without any edges crossing. In a planar graph, no two edges intersect except at their endpoints.

Euler’srule

A formula that relates the number of vertices, edges, and faces of a convex polyhedron, stating that for any polyhedron, the relationship is given by the equation V - E + F = 2, where V is the number of vertices, E is the number of edges, and F is the number of faces.

Subgraph

A graph formed from a subset of the vertices and edges of a larger graph. It retains the structure and connectivity of the original graph within that subset.

Trees

A special type of graph that is connected and acyclic, meaning it contains no cycles. Trees are characterized by having one less edge than the number of vertices, making them an essential structure in graph theory.

Bipartitegraph

A graph whose vertices can be divided into two distinct sets such that no edges connect vertices within the same set. This structure allows for two-coloring, making it useful in various applications like matching and scheduling.

Eulerian

A graph that contains a circuit which visits every edge exactly once and returns to the starting vertex, or an open trail that visits every edge exactly once. Eulerian paths and circuits are key concepts in graph theory.

Semi-Eularian

A graph that contains a trail visiting every edge exactly once but does not necessarily return to the starting vertex. Semi-Eulerian paths are fundamental in the study of traversable graphs. This type of graph features two endpoints, indicating it has exactly two vertices of odd degree.

Hamiltoniancycle

A graph cycle that visits every vertex exactly once and returns to the starting vertex. Hamiltonian cycles are significant in optimization problems and routing.

HamiltonianPath/Semi-Hamiltonian

A path in a graph that visits every vertex exactly once but does not necessarily return to the starting vertex. Hamiltonian paths are important in various applications, including network routing and scheduling.

Degree/OrderofVertex

The number of edges connected to a vertex in a graph. The degree of a vertex is crucial in understanding the graph's connectivity and structure.