Graph definition, types of graphs A graph is a data structure for storing and managing related data

Fantastic news! We've Found the answer you've been seeking!

Question:

Graph definition, types of graphs

A graph is a data structure for storing and managing related data and data relationships. A graph consists of vertices related through edges.

A vertex (or node) represents an item in a graph. In computer programming, these items are objects.
An edge represents the relationship between two vertices in a graph.
If the relationship is actually an association or a connection, where direction between two vertices does not matter, the graph could be an undirected graph. Otherwise, the graph could be a directed graph. It is also called a digraph, consisting of vertices connected by directed edges. A directed edge is a connection between a starting vertex and a terminating vertex.
A weighted graph associates a weight with each edge. A graph edge's weight, or cost, represents some numerical value between vertex items, such as flight cost between airports, the connection speed between computers, or travel time between cities. A weighted graph may be directed or undirected. Sometimes weight can also be associated with each vertex, depending on the application.
A sparse graph has far fewer edges than the maximum possible. A dense graph has the number of edges that is close to the maximal number of edges.

Adjacency, degrees, paths, cycles, and connectedness

Two vertices are adjacent if connected by an edge. The degree of a vertex of an unweighted graph is the number of edges that are incident to the vertex. The weighteddegree of a vertex of a weighted graph is the total weight of edges that are incident to the vertex.
A path is a sequence of edges leading from a source (starting) vertex to a destination (ending) vertex. The path length in an unweighted graph is the number of edges in the path. The path length in a weighted graph is the sum of the edge weights in the path.
The distance between two vertices is the number of edges on the shortest path between those vertices.
Connected: a graph is connected if, for every node, there is a way to get to every other node in the graph
Cyclic: a graph is cyclic if there is at least one cycle (the path that connects from a start node through other nodes and back to the start node). We only talk about cycles in directed graphs.
Self-loops happen when there is a link from a node to itself
The cycle length is the sum of the edge weights in a cycle. A negative edge weight cycle has a cycle length less than 0. A shortest path does not exist in a graph with a negative edge weight cycle, because each loop around the negative edge weight cycle further decreases the cycle length, so no minimum exists.