## Graph theory |

In **graph theory** is the study of * graphs*, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of

Refer to the

- definitions
- applications
- history
- graph drawing
- graph-theoretic data structures
- problems
- see also
- notes
- references
- external links

Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related

In one restricted but very common sense of the term,^{[1]}^{[2]} a **graph** is an *G* = (*V*, *E*) comprising:

*V*aset of*vertices*(also called*nodes*or*points*);*E*⊆ {{*x*,*y*} | (*x*,*y*) ∈*V*^{2}∧ x ≠ y} aset of*edges*(also called*links*or*lines*), which areunordered pairs of vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely an **undirected simple graph**.

In the edge {*x*, *y*}, the vertices *x* and *y* are called the *endpoints* of the edge. The edge is said to *join* *x* and *y* and to be *incident* on *x* and on *y*. A vertex may exist in a graph and not belong to an edge. A * loop* is an edge that joins a vertex to itself.

In one more general sense of the term allowing multiple edges,^{[3]}^{[4]} a **graph** is an ordered triple *G* = (*V*, *E*, *ϕ*) comprising:

*V*aset of*vertices*(also called*nodes*or*points*);*E*aset of*edges*(also called*links*or*lines*);*ϕ*:*E*→ {{*x*,*y*} | (*x*,*y*) ∈*V*^{2}∧ x ≠ y} an*incidence function*mapping every edge to anunordered pair of vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely an **undirected multigraph**.

Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex *x* is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph) {*x*, *x*} = {*x*} which is not in {{*x*, *y*} | (*x*, *y*) ∈ *V*^{2} ∧ x ≠ y}. So to allow loops the definitions must be expanded. For undirected simple graphs, *E* ⊆ {{*x*, *y*} | (*x*, *y*) ∈ *V*^{2} ∧ x ≠ y} should become *E* ⊆ {{*x*, *y*} | (*x*, *y*) ∈ *V*^{2}}. For undirected multigraphs, *ϕ*: *E* → {{*x*, *y*} | (*x*, *y*) ∈ *V*^{2} ∧ x ≠ y} should become *ϕ*: *E* → {{*x*, *y*} | (*x*, *y*) ∈ *V*^{2}}. To avoid ambiguity, these types of objects may be called precisely an **undirected simple graph permitting loops** and an **undirected multigraph permitting loops** respectively.

*V* and *E* are usually taken to be finite, and many of the well-known results are not true (or are rather different) for *infinite graphs* because many of the arguments fail in the *V* is often assumed to be non-empty, but *E* is allowed to be the empty set. The *order* of a graph is |*V*|, its number of vertices. The *size* of a graph is |*E*|, its number of edges. The *degree* or *valency* of a vertex is the number of edges that are incident to it, where a loop is counted twice.

In an undirected simple graph of order *n*, the maximum degree of each vertex is *n* − 1 and the maximum size of the graph is *n*(*n* − 1)/2.

The edges of an undirected simple graph permitting loops *G* induce a symmetric *G* that is called the *adjacency relation* of *G*. Specifically, for each edge {*x*, *y*}, its endpoints *x* and *y* are said to be *adjacent* to one another, which is denoted *x* ~ *y*.

A **directed graph** or **digraph** is a graph in which edges have orientations.

In one restricted but very common sense of the term,^{[5]} a **directed graph** is an ordered pair *G* = (*V*, *E*) comprising:

*V*aset of*vertices*(also called*nodes*or*points*);*E*⊆ {(*x*,*y*) | (*x*,*y*) ∈*V*^{2}∧*x*≠*y*} aset of*edges*(also called*directed edges*,*directed links*,*directed lines*,*arrows*or*arcs*) which areordered pairs of*distinct*vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely a **directed simple graph**.

In the edge (*x*, *y*) directed from *x* to *y*, the vertices *x* and *y* are called the *endpoints* of the edge, *x* the *tail* of the edge and *y* the *head* of the edge. The edge (*y*, *x*) is called the *inverted edge* of (*x*, *y*). The edge is said to *join* *x* and *y* and to be *incident* on *x* and on *y*. A vertex may exist in a graph and not belong to an edge. A * loop* is an edge that joins a vertex to itself.

In one more general sense of the term allowing multiple edges,^{[5]} a **directed graph** is an ordered triple *G* = (*V*, *E*, *ϕ*) comprising:

*V*aset of*vertices*(also called*nodes*or*points*);*E*aset of*edges*(also called*directed edges*,*directed links*,*directed lines*,*arrows*or*arcs*);*ϕ*:*E*→ {(*x*,*y*) | (*x*,*y*) ∈*V*^{2}∧ x ≠ y} an*incidence function*mapping every edge to anordered pair of*distinct*vertices (i.e., an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called precisely a **directed multigraph**.

Directed graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex *x* is the edge (for a directed simple graph) or is incident on (for a directed multigraph) (*x*, *x*) which is not in {(*x*, *y*) | (*x*, *y*) ∈ *V*^{2} ∧ *x* ≠ *y*}. So to allow loops the definitions must be expanded. For directed simple graphs, *E* ⊆ {(*x*, *y*) | (*x*, *y*) ∈ *V*^{2} ∧ x ≠ y} should become *E* ⊆ *V*^{2}. For directed multigraphs, *ϕ*: *E* → {(*x*, *y*) | (*x*, *y*) ∈ *V*^{2} ∧ x ≠ y} should become *ϕ*: *E* → *V*^{2}. To avoid ambiguity, these types of objects may be called precisely a **directed simple graph permitting loops** and a **directed multigraph permitting loops** (or a * quiver*) respectively.

The edges of a directed simple graph permitting loops *G* is a *G* that is called the *adjacency relation* of *G*. Specifically, for each edge (*x*, *y*), its endpoints *x* and *y* are said to be *adjacent* to one another, which is denoted *x* ~ *y*.

Other Languages

አማርኛ: ሥነ ግራፍ

العربية: نظرية المخططات

aragonés: Teoría de grafos

asturianu: Teoría de grafos

বাংলা: গ্রাফ তত্ত্ব

башҡортса: Графтар теорияһы

беларуская: Тэорыя графаў

български: Теория на графите

bosanski: Teorija grafikona

català: Teoria de grafs

Чӑвашла: Графсен теорийĕ

čeština: Teorie grafů

Cymraeg: Damcaniaeth graffiau

dansk: Grafteori

Deutsch: Graphentheorie

eesti: Graafiteooria

Ελληνικά: Θεωρία γράφων

español: Teoría de grafos

Esperanto: Grafeteorio

euskara: Grafo teoria

فارسی: نظریه گراف

français: Théorie des graphes

galego: Teoría de grafos

한국어: 그래프 이론

հայերեն: Գրաֆների տեսություն

हिन्दी: ग्राफ़ सिद्धान्त

Bahasa Indonesia: Teori graf

íslenska: Netafræði

italiano: Teoria dei grafi

עברית: תורת הגרפים

қазақша: Графтар теориясы

Кыргызча: Графтар теориясы

latviešu: Grafu teorija

lietuvių: Grafų teorija

magyar: Gráfelmélet

македонски: Теорија на графови

Malti: Teorija tal-grafi

Bahasa Melayu: Teori graf

монгол: Графын онол

Nederlands: Grafentheorie

日本語: グラフ理論

norsk: Grafteori

norsk nynorsk: Grafteori

polski: Teoria grafów

português: Teoria dos grafos

română: Teoria grafurilor

русский: Теория графов

sicilianu: Tiuria dî grafi

Simple English: Graph theory

slovenčina: Teória grafov

slovenščina: Teorija grafov

کوردی: تیۆریی گراف

српски / srpski: Теорија графова

srpskohrvatski / српскохрватски: Teorija grafova

suomi: Verkkoteoria

svenska: Grafteori

Tagalog: Teoriya ng grap

ไทย: ทฤษฎีกราฟ

тоҷикӣ: Назарияи графҳо

Türkçe: Çizge teorisi

українська: Теорія графів

اردو: نظریۂ گراف

Tiếng Việt: Lý thuyết đồ thị

吴语: 图论

粵語: 圖論

中文: 图论