Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Graph (graph theory)"

(→‎Trees)
m (→‎Bipartite graph)
 
(10 intermediate revisions by 5 users not shown)
Line 3: Line 3:
 
{{image}}
 
{{image}}
  
−
Formally, a graph <math>G</math> is a pair, <math>G = (V, E)</math>, of a set <math>V</math> of vertices together with a subset <math>E</math> of pairs of elements of <math>V</math>.  Note that this definition describes ''simple, loopless'' graphs: there is at most one edge joining two vertices, and no edge may join a vertex to itself.  For graphs with multiple edges, see [[multigraph]].
+
Formally, a graph <math>G</math> is a pair, <math>G = (V, E)</math>, of a set <math>V</math> of vertices together with a [[class]] of subsets <math>E</math> made up of pairs of elements from <math>V</math>.  Note that this definition describes ''simple, loopless'' graphs: there is at most one edge joining two vertices, no edge may join a vertex to itself, and the edges are not directed.  For graphs with multiple edges, see [[multigraph]]. If the edges are directed, then <math>E</math> may be defined using ordered pairs from the [[product set]] <math>V \times V</math>.
  
−
==Important Related Definitions==
+
==Definitions==
 
* If <math>v \in V</math>, <math>e \in E</math> and <math>v \in e</math> then we say <math>e</math> and <math>v</math> are ''incident.''  If <math>e, f \in E</math> and <math>v \in e, f</math> we say the edges <math>e</math> and <math>f</math> are ''coincident'' at <math>v</math>.
 
* If <math>v \in V</math>, <math>e \in E</math> and <math>v \in e</math> then we say <math>e</math> and <math>v</math> are ''incident.''  If <math>e, f \in E</math> and <math>v \in e, f</math> we say the edges <math>e</math> and <math>f</math> are ''coincident'' at <math>v</math>.
 
* The number of edges in <math>E</math> containing <math>v</math> is the ''degree'' of <math>v</math> and is often denoted <math>d(v)</math>.
 
* The number of edges in <math>E</math> containing <math>v</math> is the ''degree'' of <math>v</math> and is often denoted <math>d(v)</math>.
Line 13: Line 13:
 
==Types of Graphs and Subgraphs==
 
==Types of Graphs and Subgraphs==
 
===Complete Graph or Clique===
 
===Complete Graph or Clique===
−
A ''complete graph'' is a graph in which there is an edge joining every pair of vertices is connected.  The complete graph on <math>n</math> vertices is denoted <math>K_n</math>.  If <math>H</math> is a complete subgraph of <math>G</math> then the vertices of <math>H</math> are said to form a ''clique'' in <math>G</math>.
+
A ''complete graph'' is a graph in which there is an edge joining every pair of vertices is connected.  The complete graph on <math>n</math> vertices is denoted <math>K_n</math>, and has <math>\binom{n}{2} = \frac{n(n-1)}{2}</math> edges.  If <math>H</math> is a complete subgraph of <math>G</math> then the vertices of <math>H</math> are said to form a ''clique'' in <math>G</math>.
  
−
===Complementrary Graphs===
+
===Complementary Graphs===
 
If <math>G_1 = (V, E_1)</math> and <math>G_2 = (V, E_2)</math> are two graphs on the same vertex set such that <math>G = (V, E_1 \cup E_2)</math> is a complete graph and <math>E_1 \cap E_2 = \emptyset</math> then <math>G_2</math> is said to be the ''complement'' of <math>G_1</math> and vice-versa.
 
If <math>G_1 = (V, E_1)</math> and <math>G_2 = (V, E_2)</math> are two graphs on the same vertex set such that <math>G = (V, E_1 \cup E_2)</math> is a complete graph and <math>E_1 \cap E_2 = \emptyset</math> then <math>G_2</math> is said to be the ''complement'' of <math>G_1</math> and vice-versa.
  
Line 21: Line 21:
 
A ''null graph'' (or ''independent set'') is the complement of a complete graph.  Equivalently, a null graph is a graph in which every vertex is isolated.  When drawn in the usual fashion, a null graph is simply a collection of scattered points (the vertices) with no edges connecting them.  The terminology "independent set" is used most frequently to refer to a subgraph.  In other words, one says <math>V_1 \subseteq V_1</math> is an independent set in <math>G= (V, E)</math> if and only if <math>V_1</math> is a clique in the complement of <math>G</math>.
 
A ''null graph'' (or ''independent set'') is the complement of a complete graph.  Equivalently, a null graph is a graph in which every vertex is isolated.  When drawn in the usual fashion, a null graph is simply a collection of scattered points (the vertices) with no edges connecting them.  The terminology "independent set" is used most frequently to refer to a subgraph.  In other words, one says <math>V_1 \subseteq V_1</math> is an independent set in <math>G= (V, E)</math> if and only if <math>V_1</math> is a clique in the complement of <math>G</math>.
  
−
===Paths and Cycles===
+
===Connected Graph===
−
A ''path'' in a graph <math>G = (V, E)</math> is a sequence <math>v_0, e_1, v_1, \ldots, e_n, v_n</math> such that <math>v_i \in V</math>, <math>e_i \in E</math> and <math>e_i = \{v_{i - 1}, v_i\}</math> for all <math>i</math>.  A ''cycle'' is a path in which the initial and final vertices are the same.
+
An undirected graph <math>G</math> is ''connected'' if for all <math>u, v \in V</math>, there exists a path from <math>u</math> to <math>v</math> using only edges in <math>G</math>.  That is, there are no isolated vertices with no paths coming from them, nor can the vertex set be partitioned into two parts with no edge between them. A related concept is a ''connected component'', which is a maximally connected subgraph of a graph.
  
−
===Connected Graph===
+
===Strongly Connected Graph===
−
A graph is ''connected'' if any two vertices can be connected by a path.  That is, there are no isolated vertices with no paths coming from them, nor can the vertex set be partitioned into two parts with no edge between them.
+
A directed graph <math>G</math> is ''strongly connected'' if for all <math>u, v \in V</math>, there exists a ''directed'' path from <math>u</math> to <math>v</math> using only edges in <math>G</math>.
  
 
===Planar Graphs===
 
===Planar Graphs===
−
A graph is said to be planar if it can be drawn in a [[plane]] with no intersecting edges. For example, <math>K_1,K_2,K_3,</math> and <math>K_4</math> are planar.
+
A graph is said to be planar if it can be drawn in a [[plane]] with no intersecting edges. For example, <math>K_1,K_2,K_3,</math> and <math>K_4</math> are planar, but <math>K_5</math> and <math>K_{3,3}</math> are not planar.
  
 
{{image}}
 
{{image}}
Line 45: Line 45:
  
 
===Bipartite graph===
 
===Bipartite graph===
−
A graph is called bipartite if its vertex set can be split into two disjoint subsets such that no edge exists within each subset. A graph is bipartite if and only if it has no odd cycles, which is related to the Two Color Theorem. Bipartite graphs have many applications including matching problems.
+
A graph is called ''bipartite'' if its vertex set can be split into two disjoint subsets <math>L</math> and <math>R</math> such that every edge connects a vertex in <math>L</math> to a vertex in <math>R</math> (by this definition, the empty graph on <math>n</math> vertices is bipartite). A graph <math>G</math> is bipartite if and only if it has no odd cycles, if and only if <math>G</math> is 2-colorable. Bipartite graphs have many applications including matching problems.
 +
 
 +
The ''complete bipartite graph'' (denoted <math>K_{m,n}</math> for integers <math>m</math> and <math>n</math>) is a bipartite graph where <math>|L| = m</math>, <math>|R| = n</math>, and there is an edge connecting every <math>u \in L</math> to every <math>v \in R</math> (so that <math>K_{m,n}</math> has <math>mn</math> edges).
 +
 
 +
{{image}}
 +
 
 +
==Walks==
 +
A walk is the general process of moving along the edges of a graph. A path does not go through any vertex more than once, while a trail does not go through any edge more than once
 +
 
 +
===Paths and Cycles===
 +
A ''path'' in a graph <math>G = (V, E)</math> is a sequence <math>v_0, e_1, v_1, \ldots, e_n, v_n</math> such that <math>v_i \in V</math>, <math>e_i \in E</math> and <math>e_i = \{v_{i - 1}, v_i\}</math> for all <math>i</math>.  A ''cycle'' is a path in which the initial and final vertices are the same.
 +
 
 
===Euler Trail===
 
===Euler Trail===
 
A Euler trail is a graph where it is possible to form a trail which uses all the edges. A Euler trail has at most two vertices with odd degrees. The sum of all the degrees of the vertices equals twice the number of edges in the graph.  
 
A Euler trail is a graph where it is possible to form a trail which uses all the edges. A Euler trail has at most two vertices with odd degrees. The sum of all the degrees of the vertices equals twice the number of edges in the graph.  
Line 51: Line 62:
 
A ''forest'' is a graph which does not have any cycles.  A ''[[tree (graph theory) | tree]]'' is a connected forest.
 
A ''forest'' is a graph which does not have any cycles.  A ''[[tree (graph theory) | tree]]'' is a connected forest.
  
−
===Weighted Graphs===
+
==Weighted Graphs==
−
The edges of a graph can have weights assigned to them that represent some abstract relative value.
+
The edges of a graph can have weights assigned to them that represent some value or "cost" (such as distance). For example, Dijkstra's algorithm, which computes the shortest path from a source vertex <math>s \in V</math> to all vertices in <math>v \in V</math>, runs on a graph whose edge weights are non-negative.
  
−
===Hypergraph===
+
==Hypergraph==
 
A hypergraph is an extension of the concept of a graph where the edges can encompass more than two vertices, and essentially become sets themselves. Hypergraph theory is often difficult to visualize, and thus is often studied based on the sets that make it up.
 
A hypergraph is an extension of the concept of a graph where the edges can encompass more than two vertices, and essentially become sets themselves. Hypergraph theory is often difficult to visualize, and thus is often studied based on the sets that make it up.
  

Latest revision as of 09:26, 27 August 2020

In graph theory, a graph is a (usually finite) nonempty set of vertices that are joined by a number (possibly zero) of edges. Graphs are frequently represented graphically, with the vertices as points and the edges as smooth curves joining pairs of vertices.

An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.

Formally, a graph $G$ is a pair, $G = (V, E)$, of a set $V$ of vertices together with a class of subsets $E$ made up of pairs of elements from $V$. Note that this definition describes simple, loopless graphs: there is at most one edge joining two vertices, no edge may join a vertex to itself, and the edges are not directed. For graphs with multiple edges, see multigraph. If the edges are directed, then $E$ may be defined using ordered pairs from the product set $V \times V$.

Definitions

  • If $v \in V$, $e \in E$ and $v \in e$ then we say $e$ and $v$ are incident. If $e, f \in E$ and $v \in e, f$ we say the edges $e$ and $f$ are coincident at $v$.
  • The number of edges in $E$ containing $v$ is the degree of $v$ and is often denoted $d(v)$.
  • A vertex $v$ is isolated if $d(v) = 0$, i.e. if there are no edges incident to $v$.
  • If $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are graphs such that $V_2 \subseteq V_1$ and $E_2 \subseteq E_1$ then we say $G_2$ is a subgraph of $G_1$. If $E_2 = \{\{v_1, v_2\} \mid \{v_1, v_2\} \in E \textrm{ and } v_1, v_2 \in V_2$ (informally, if $E_2$ contains all those edges of $E_1$ whose vertices are in $V_2$) then we say that $G_2$ is an induced subgraph of $G_1$.

Types of Graphs and Subgraphs

Complete Graph or Clique

A complete graph is a graph in which there is an edge joining every pair of vertices is connected. The complete graph on $n$ vertices is denoted $K_n$, and has $\binom{n}{2} = \frac{n(n-1)}{2}$ edges. If $H$ is a complete subgraph of $G$ then the vertices of $H$ are said to form a clique in $G$.

Complementary Graphs

If $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ are two graphs on the same vertex set such that $G = (V, E_1 \cup E_2)$ is a complete graph and $E_1 \cap E_2 = \emptyset$ then $G_2$ is said to be the complement of $G_1$ and vice-versa.

Null Graph or Independent Set

A null graph (or independent set) is the complement of a complete graph. Equivalently, a null graph is a graph in which every vertex is isolated. When drawn in the usual fashion, a null graph is simply a collection of scattered points (the vertices) with no edges connecting them. The terminology "independent set" is used most frequently to refer to a subgraph. In other words, one says $V_1 \subseteq V_1$ is an independent set in $G= (V, E)$ if and only if $V_1$ is a clique in the complement of $G$.

Connected Graph

An undirected graph $G$ is connected if for all $u, v \in V$, there exists a path from $u$ to $v$ using only edges in $G$. That is, there are no isolated vertices with no paths coming from them, nor can the vertex set be partitioned into two parts with no edge between them. A related concept is a connected component, which is a maximally connected subgraph of a graph.

Strongly Connected Graph

A directed graph $G$ is strongly connected if for all $u, v \in V$, there exists a directed path from $u$ to $v$ using only edges in $G$.

Planar Graphs

A graph is said to be planar if it can be drawn in a plane with no intersecting edges. For example, $K_1,K_2,K_3,$ and $K_4$ are planar, but $K_5$ and $K_{3,3}$ are not planar.

An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.

In a planar graph, we can define faces of the graph, or the smallest regions bounded by edges. (An alternate definition is the regions bounded by edges which do not have any edges going through them.) Note that the area outside the planar graph is also a face, called the unbounded face. The degree of the face is the number of edges that bound the face. (Note that the same term is used for vertices, which can become confusing)

All planar graphs have dual graphs, which involve turning the planes of one graph into vertices, and the vertics into planes, with edges connecting if two planes are adjacent. The dual of the dual of a graph is returns the original graph.

An interesting result is Euler's Polyhedral Formula, which states that in a planar graph with $V$ vertices, $E$ edges, and $F$ faces, then \[V-E+F=2\] The proof of this is simple using induction, but the derivation of the formula is much trickier.

Other interesting results for planar graphs are that:

  • $E\le 3V-6$
  • if the the sum of the degrees of the faces of the graph is $F$, then $F\le \frac{2}{3}E$.

Bipartite graph

A graph is called bipartite if its vertex set can be split into two disjoint subsets $L$ and $R$ such that every edge connects a vertex in $L$ to a vertex in $R$ (by this definition, the empty graph on $n$ vertices is bipartite). A graph $G$ is bipartite if and only if it has no odd cycles, if and only if $G$ is 2-colorable. Bipartite graphs have many applications including matching problems.

The complete bipartite graph (denoted $K_{m,n}$ for integers $m$ and $n$) is a bipartite graph where $|L| = m$, $|R| = n$, and there is an edge connecting every $u \in L$ to every $v \in R$ (so that $K_{m,n}$ has $mn$ edges).

An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.

Walks

A walk is the general process of moving along the edges of a graph. A path does not go through any vertex more than once, while a trail does not go through any edge more than once

Paths and Cycles

A path in a graph $G = (V, E)$ is a sequence $v_0, e_1, v_1, \ldots, e_n, v_n$ such that $v_i \in V$, $e_i \in E$ and $e_i = \{v_{i - 1}, v_i\}$ for all $i$. A cycle is a path in which the initial and final vertices are the same.

Euler Trail

A Euler trail is a graph where it is possible to form a trail which uses all the edges. A Euler trail has at most two vertices with odd degrees. The sum of all the degrees of the vertices equals twice the number of edges in the graph.

Trees and Forests

A forest is a graph which does not have any cycles. A tree is a connected forest.

Weighted Graphs

The edges of a graph can have weights assigned to them that represent some value or "cost" (such as distance). For example, Dijkstra's algorithm, which computes the shortest path from a source vertex $s \in V$ to all vertices in $v \in V$, runs on a graph whose edge weights are non-negative.

Hypergraph

A hypergraph is an extension of the concept of a graph where the edges can encompass more than two vertices, and essentially become sets themselves. Hypergraph theory is often difficult to visualize, and thus is often studied based on the sets that make it up.


See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Graph_(graph_theory)&oldid=132607"