Graph Concepts: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 14: Line 14:
==Directed Graph==
==Directed Graph==
==Undirected Graph==
==Undirected Graph==
=Graph Density=
==Sparse Graphs==
==Dense Graphs==

Revision as of 19:52, 1 October 2021

Internal

Graph Definition

A graph is a pair-wise relationship among a set of objects. Mathematically, a graph G is a pair (V, E), where V is a finite set of vertices, called the vertex set of G, and E is a binary relation on G, called the edge set of G, which contains the graph's edges.

n and m Convention

In graph problems, the usual convention is to denote the number of vertices with n and the number of edges with m. In most, but not all, applications, m is Ω(n) and O(n2). Also see sparse graphs and dense graphs.

Vertex (Node)

An elements of the vertex set V is called vertex (plural vertices). An alternate term for vertex, used sometimes in the graph theory literature, is node. We prefer to use the term "node" when we refer to the vertices of rooted trees. We use "vertex" as a more generic term that refers to graphs in general. Another alternate name is entity.

Edge (Arc)

The element of the edge set E are called edges (also known as relationships or arcs). By convention, we use (u, v) notation for an edge, where u and v represent vertices in V. The order in which vertices are specified for an edge may be relevant. If the order in which the vertices are specified matters, then the graph is a directed graph. If the order in which the vertices are specified does not matter, then the graph is an undirected graph.

Graph Directionality

Directed Graph

Undirected Graph

Graph Density

Sparse Graphs

Dense Graphs