Studied by 35 people
Trail
A walk in which no edge is repeated
Path
A walk in which no edge or vertex is repeated
Circuit
A trail that starts and finishes at the same vertex
Cycle
A circuit in which no vertex is repeated
Graph
A collection of vertices connected by edges, used to represent relationships in various structures.
Vertices
The fundamental units of a graph, representing points or nodes that can be connected by edges.
Edges
Connections between vertices in a graph, representing relationships or paths.
Walk
A sequence of vertices in a graph where each adjacent pair is connected by an edge. A walk can revisit vertices and edges.
Adjacency table
A data structure used to represent a graph, where each row and column corresponds to a vertex, indicating whether pairs of vertices are adjacent.
Connected graph
A graph in which there is a path between every pair of vertices, ensuring that all vertices are reachable from one another.
Subgraph
A graph formed from a subset of the vertices and edges of a larger graph, maintaining the connections between the chosen vertices.
Unconnected graph
A graph that consists of two or more components, meaning there are at least two vertices that are not connected by a path.
Direct
a graph where there is a directed edge between pairs of vertices, indicating a one-way relationship.
Connected
A type of graph in which there is a path between every pair of vertices, ensuring all vertices are reachable from one another.
Strongly connected
A directed graph where there is a directed path from every vertex to every other vertex. This means every pair of vertices is mutually reachable.
Degree
The number of edges incident to a vertex in a graph, indicating how many connections it has.
Even degree
A vertex in a graph has an even degree if it is connected to an even number of edges.
In degree
The number of edges directed into a vertex in a directed graph.
Out degree
The number of edges directed away from a vertex in a directed graph.
Loop
An edge from a vertex back to itself
Simple graph
One with no loops or multiple edges
Multigraph
Multiple edges between vertices
Tree
A connected graph with no cycles.
Eulerian circuit
A circuit which transverses every edge exactly once
Eulerian trail
A trail which transverses every edge exactly once, but does not start and end at the same vertex
A connected graph is Eulerian if…
there are no vertices of odd degree
A connected graph is semi-Eulerian if..
there are exactly two vertices of odd degree
Hamiltonian cycle
A cycle which visits each vertex exactly once
Hamiltonian path
A path which visits each vertex exactly once, but doesn’t start and end at the same vertex
Walk
A sequence of vertices such that each successive pair of vertices is adjacent
