在數學中，圖論是對圖的研究，圖是用來模擬物體之間兩兩關係的數學結構。在此上下文中，圖由頂點、節點或由邊、弧或線連接的點組成。
一個圖可能是無向的，這意味著與每條邊相關的兩個頂點之間沒有區別，或者它的邊可能從一個頂點指向另一個頂點;參見圖(離散數學)了解更多詳細的定義，以及通常考慮的圖類型的其他變化。
圖是離散數學的主要研究對象之一。
In mathematics graph theoryis the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines.
A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another; see Graph (discrete mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered.
Graphs are one of the prime objects of study in discrete mathematics.
有關圖論的基本定義，請參閱圖論術語表。
Refer to the glossary of graph theory for basic definitions in graph theory.
一個圖的圖畫 A drawing of a graph
01
—
定義 Definitions
圖論中的定義各不相同。下面是定義圖形和相關數學結構的一些更基本的方法。
Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures.
圖 Graph
在最普遍的意義上的術語,圖是一個有序對G = (V, E)由一組頂點V或節點或邊緣點的一組E或弧行,這是2-element V的子集(即一條邊與兩個頂點相關聯,這協會的無序對由兩個頂點)。
為了避免歧義，可以將這種類型的圖精確地描述為無向且簡單。
In the most common sense of the term, a graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes or points together with a set E of edges or arcs or lines, which are 2-element subsets of V (i.e. an edge is associated with two vertices, and that association takes the form of the unordered pair comprising those two vertices). To avoid ambiguity, this type of graph may be described precisely as undirected and simple.
圖的其他意義來自於對邊集的不同概念。
在一個更廣義的概念中，V是一個集合，它與每條邊與兩個頂點的關聯的關聯關係。
在另一個廣義的概念中，E是一個由無序的(不一定是不同的)頂點組成的多對集合。
許多作者稱這種類型的對象為多重圖或偽圖。
Other senses of graph stem from different conceptions of the edge set. In one more generalized notion, V is a set together with a relation of incidence that associates with each edge two vertices. In another generalized notion, E is a multiset of unordered pairs of (not necessarily distinct) vertices. Many authors call this type of object a multigraph or pseudograph.
所有這些變量和其他變量將在下面詳細描述。
All of these variants and others are described more fully below.
屬於邊的頂點稱為邊的末端或邊的末端頂點。
一個頂點可能存在於一個圖中而不屬於一條邊。
The vertices belonging to an edge are called the ends or end vertices of the edge. A vertex may exist in a graph and not belong to an edge.
V和E通常被認為是有限的，對於無限圖，許多眾所周知的結果都是不正確的(或者是相當不同的)，因為許多參數在無限情況下失敗了。
圖的順序是|V|，它的頂點數。
圖的大小是|E|，它的邊的數目。
一個頂點的度或價是連接到它的邊的數量，其中連接一個頂點到它自身的邊(循環)被計數兩次。
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 infinite case.
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 connect to it, where an edge that connects a vertex to itself (a loop) is counted twice.
對於邊{x, y}，圖理論家通常使用稍微短一些的符號xy。
For an edge {x, y}, graph theorists usually use the somewhat shorter notation xy.
02
—
應用 Applications
在物理、生物、社會和信息系統中，圖可以用來建模許多類型的關係和過程。許多實際問題可以用圖表來表示。
為了強調它們在實際系統中的應用，網絡這個術語有時被定義為一個圖，其中的屬性(例如名稱)與節點和/或邊相關聯。
Graphs can be used to model many types of relations and processes in physical, biological, social and information systems. Many practical problems can be represented by graphs.
Emphasizing their application to real-world systems, the term network is sometimes defined to mean a graph in which attributes (e.g. names) are associated with the nodes and/or edges.
在計算機科學中，圖被用來表示通信網絡、數據組織、計算設備、計算流程等。例如，一個網站的連結結構可以用一個有向圖表示，其中頂點表示網頁，有向邊表示從一個頁面到另一個頁面的連結。
類似的方法可以應用到社交媒體、旅遊、生物、計算機晶片設計和許多其他領域。因此，開發處理圖形的算法是計算機科學的主要興趣所在。
圖的變換通常是形式化的，並由圖形重寫系統表示。
與側重於基於規則的圖形內存操作的圖形轉換系統相輔相成的是面向事務安全、持久存儲和查詢圖形結構數據的圖形資料庫。
In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the link structure of a website can be represented by a directed graph, in which the vertices represent web pages and directed edges represent links from one page to another.
A similar approach can be taken to problems in social media, travel, biology, computer chip design, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science.
The transformation of graphs is often formalized and represented by graph rewrite systems. Complementary to graph transformation systems focusing on rule-based in-memory manipulation of graphs are graph databases geared towards transaction-safe, persistent storing and querying of graph-structured data.
各種形式的圖論方法已證明在語言學中特別有用，因為自然語言常常適合於離散結構。傳統上，語法和組合語義遵循基於樹的結構，其表達能力取決於組合原則，在層次圖中建模。
更現代的方法，如頭驅短語結構語法，使用類型化特徵結構對自然語言的語法建模，這些特徵結構是有向無環圖。在詞彙語義學中，特別是在計算機上，當一個給定的單詞被相關的單詞理解時，對單詞意義的建模就更容易了;因此，語義網絡在計算語言學中非常重要。
音系學中的其他方法(例如，使用格點圖的最優性理論)和形態學(例如，使用有限狀態形態學，使用有限狀態傳感器)在語言作為圖的分析中也很常見。
事實上，這一數學領域對語言學的有用性催生了一些組織，如文本圖，以及各種「網絡」項目，如WordNet、VerbNet等。
Graph-theoretic methods, in various forms, have proven particularly useful in linguistics, since natural language often lends itself well to discrete structure. Traditionally, syntax and compositional semantics follow tree-based structures, whose expressive power lies in the principle of compositionality, modeled in a hierarchical graph.
More contemporary approaches such as head-driven phrase structure grammar model the syntax of natural language using typed feature structures, which are directed acyclic graphs. Within lexical semantics, especially as applied to computers, modeling word meaning is easier when a given word is understood in terms of related words; semantic networks are therefore important in computational linguistics.
Still other methods in phonology (e.g. optimality theory, which uses lattice graphs) and morphology (e.g. finite-state morphology, using finite-state transducers) are common in the analysis of language as a graph. Indeed, the usefulness of this area of mathematics to linguistics has borne organizations such as TextGraphs, as well as various 'Net' projects, such as WordNet, VerbNet, and others.
圖論也被用來研究化學和物理中的分子。摘要在凝聚態物理中，通過收集與原子拓撲有關的圖論性質的統計量，可以定量地研究複雜的模擬原子結構的三維結構。
在化學中，圖是分子的自然模型，頂點表示原子，邊表示鍵。這種方法特別用於分子結構的計算機處理，從化學編輯器到資料庫搜索。
在統計物理學中，圖可以表示系統相互作用部分之間的局部連接，以及系統上物理過程的動態。類似地，在計算神經科學中，圖形可以用來表示大腦區域之間的功能連接，這些區域相互作用產生各種認知過程，其中頂點代表大腦的不同區域，而邊緣代表這些區域之間的連接。
圖也用來表示多孔介質的微尺度通道，其中頂點表示孔隙，邊表示連接孔隙的較小通道。
Graph theory is also used to study molecules in chemistry and physics. In condensed matter physics, the three-dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms.
In chemistry a graph makes a natural model for a molecule, where vertices represent atoms and edges bonds. This approach is especially used in computer processing of molecular structures, ranging from chemical editors to database searching.
In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems. Similarly, in computational neuroscience graphs can be used to represent functional connections between brain areas that interact to give rise to various cognitive processes, where the vertices represent different areas of the brain and the edges represent the connections between those areas.
Graphs are also used to represent the micro-scale channels of porous media, in which the vertices represent the pores and the edges represent the smaller channels connecting the pores.
由維基百科編輯(邊)組成的網絡圖，在2013年夏季的一個月內貢獻了不同的維基百科語言版本(頂點)The network graph formed by Wikipedia editors (edges) contributing to different Wikipedia language versions (vertices) during one month in summer 2013
圖論也被廣泛地應用於社會學中，作為一種衡量演員聲望或探索謠言傳播的方法，特別是通過使用社會網絡分析軟體。在社交網絡的保護傘下，有許多不同類型的圖表。
熟人圖和友誼圖描述的是人們是否互相認識。
影響圖是一種模型，用來描述某個人是否能夠影響其他人的行為。
最後，協作圖建模兩個人是否以特定的方式一起工作，例如一起在電影中表演。
Graph theory is also widely used in sociology as a way, for example, to measure actors' prestige or to explore rumor spreading, notably through the use of social network analysis software. Under the umbrella of social networks are many different types of graphs.
Acquaintanceship and friendship graphs describe whether people know each other. Influence graphs model whether certain people can influence the behavior of others. Finally, collaboration graphs model whether two people work together in a particular way, such as acting in a movie together.
同樣，圖論在生物學和保護工作中也很有用，其中一個頂點可以表示某些物種存在(或棲息)的區域，而邊緣則表示遷移路徑，或區域間的移動。
當觀察繁殖模式或跟蹤疾病、寄生蟲的傳播或運動的變化如何影響其他物種時，這些信息是很重要的。
Likewise, graph theory is useful in biology and conservation efforts where a vertex can represent regions where certain species exist (or inhabit) and the edges represent migration paths, or movement between the regions. This information is important when looking at breeding patterns or tracking the spread of disease, parasites or how changes to the movement can affect other species.
在數學中，圖形在幾何學和拓撲的某些部分(如紐結理論)中是有用的。
代數圖論與群論有著密切的聯繫。
In mathematics, graphs are useful in geometry and certain parts of topology such as knot theory. Algebraic graph theory has close links with group theory.
可以通過為圖的每條邊分配一個權重來擴展圖結構。
帶有權值的圖，或稱加權圖，用於表示成對連接具有某些數值的結構。
例如，如果一個圖表示一個道路網絡，那麼權值可以表示每條道路的長度。
A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example, if a graph represents a road network, the weights could represent the length of each road.
社會學中的圖論:莫雷諾社會圖(1953)
Graph theory in sociology: MorenoSociogram (1953)
03
—
歷史 History
萊昂哈德·歐拉於1736年發表的《哥尼斯堡七座橋》被認為是圖論史上的第一篇論文。本文與範德蒙德關於騎士問題的論文一樣，繼續進行萊布尼茨提出的situs分析。
摘要利用柯西和L'Huillier對凸多面體邊數、頂點數和面數的歐拉公式進行了研究和推廣，代表了拓撲學這一數學分支的開端。
The paper written by Leonhard Euler on the Seven Bridges of Knigsberg and published in 1736 is regarded as the first paper in the history of graph theory. This paper, as well as the one written by Vandermonde on the knight problem, carried on with the analysis situs initiated by Leibniz.
Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by Cauchy and L'Huillier, and represents the beginning of the branch of mathematics known as topology.
在歐拉關於哥尼斯堡橋的論文發表一個多世紀之後，當李斯特引入拓撲的概念時，Cayley被由微分學產生的特殊解析形式的興趣所引導，去研究一類特殊的圖——樹。這項研究對理論化學有許多啟示。
他使用的技術主要涉及具有特定屬性的圖的枚舉。
計數圖理論是由Cayley的研究結果和1935年至1937年Polya發表的基礎研究結果而產生的。
數學和化學思想的融合開始成為圖論標準術語的一部分。
More than one century after Euler's paper on the bridges of Knigsberg and while Listing was introducing the concept of topology, Cayley was led by an interest in particular analytical forms arising from differential calculus to study a particular class of graphs, the trees. This study had many implications for theoretical chemistry.
The techniques he used mainly concern the enumeration of graphs with particular properties. Enumerative graph theory then arose from the results of Cayley and the fundamental results published by Pólya between 1935 and 1937. These were generalized by De Bruijn in 1959.
Cayley linked his results on trees with contemporary studies of chemical composition.
The fusion of ideas from mathematics with those from chemistry began what has become part of the standard terminology of graph theory.
特別是，西爾維斯特在1878年發表於《自然》雜誌上的一篇論文中引入了「圖」一詞，他將代數和分子圖中的「數量不變量」和「共變量」進行了類比:
In particular, the term "graph" was introduced by Sylvester in a paper published in 1878 in Nature, where he draws an analogy between "quantic invariants" and "co-variants" of algebra and molecular diagrams:
"因此，每一個不變量和協變都可以用與凱庫爾圖或化學圖完全相同的圖形來表示。[…]我給出了圖的幾何乘法的一個規則，即構造一個圖到其各自的圖的同變或同變的乘積。[……]」(斜體字與原文相同)。
"[…] Every invariant and co-variant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph. […] I give a rule for the geometrical multiplication of graphs, i.e. for constructing a graph to the product of in- or co-variants whose separate graphs are given. […]" (italics as in the original).
圖論的第一本教材是由窩Knig,並於1936年出版。
Frank Harary在1969年出版的另一本書「被認為是世界上關於這一主題的權威教科書」，它使數學家、化學家、電氣工程師和社會科學家能夠相互交流。
哈裡把所有的版稅都捐給了Polya獎。
The first textbook on graph theory was written by Dénes Knig, and published in 1936. Another book by Frank Harary, published in 1969, was "considered the world over to be the definitive textbook on the subject", and enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other. Harary donated all of the royalties to fund the Pólya Prize.
圖論中最著名和最具啟發性的問題之一是四色問題:「平面上繪製的任何地圖，其區域都可能被塗上四種顏色，以至於任何兩個邊界相同的區域都有不同的顏色，這是真的嗎?」
這個問題最早是由弗朗西斯·格思裡在1852年提出的，它的第一個書面記錄是在同年德·摩根寫給漢密爾頓的一封信中。提出了許多不正確的證明，包括Cayley、Kempe等人的證明。
Tait、Heawood、Ramsey和Hadwiger對這個問題的研究和推廣導致了對任意屬曲面上嵌入圖的著色的研究。
泰特的再形成生成一個新類的問題,分解問題,特別是研究了彼得森和Knig。
拉姆齊關於著色的著作，尤其是圖蘭在1941年獲得的結果，是圖論的另一個分支——極值圖論的起源。
One of the most famous and stimulating problems in graph theory is the four color problem: "Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?"
This problem was first posed by Francis Guthrie in 1852 and its first written record is in a letter of De Morgan addressed to Hamilton the same year. Many incorrect proofs have been proposed, including those by Cayley, Kempe, and others.
The study and the generalization of this problem by Tait, Heawood, Ramsey and Hadwiger led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus. Tait's reformulation generated a new class of problems, the factorization problems, particularly studied by Petersen and Knig.
The works of Ramsey on colorations and more specially the results obtained by Turán in 1941 was at the origin of another branch of graph theory, extremal graph theory.
一個多世紀以來，四色問題一直沒有得到解決。1969年，海因裡希·希斯發表了一種用計算機解決這個問題的方法。1976年，肯尼斯·阿佩爾(Kenneth Appel)和沃爾夫岡·哈肯(Wolfgang Haken)製作了一份計算機輔助證明，從根本上利用了Heesch提出的「放電」概念。
該證明涉及到用計算機檢查1936種構型的性質，由於其複雜性，當時沒有被完全接受。
20年後，羅伯遜、西摩、桑德斯和託馬斯給出了一個只考慮633種構型的更簡單的證明。
The four color problem remained unsolved for more than a century. In 1969 Heinrich Heesch published a method for solving the problem using computers. A computer-aided proof produced in 1976 by Kenneth Appel and Wolfgang Haken makes fundamental use of the notion of "discharging" developed by Heesch.
The proof involved checking the properties of 1,936 configurations by computer, and was not fully accepted at the time due to its complexity. A simpler proof considering only 633 configurations was given twenty years later by Robertson, Seymour, Sanders and Thomas.
拓撲學從1860年到1930年的自主發展，通過Jordan, Kuratowski和Whitney的作品，為圖論提供了豐富的知識。圖論和拓撲學共同發展的另一個重要因素來自於現代代數技術的使用。
這種用法的第一個例子來自物理學家古斯塔夫·基爾霍夫(Gustav Kirchhoff)的著作，他在1845年發表了基爾霍夫電路定律(Kirchhoff's circuit laws)，用於計算電路中的電壓和電流。
The autonomous development of topology from 1860 and 1930 fertilized graph theory back through the works of Jordan, Kuratowski and Whitney. Another important factor of common development of graph theory and topology came from the use of the techniques of modern algebra.
The first example of such a use comes from the work of the physicist Gustav Kirchhoff, who published in 1845 his Kirchhoff's circuit laws for calculating the voltage and current in electric circuits.
概率方法在圖論的引入,尤其是在研究Erds和Renyi漸近的概率圖的連通性,引發了另一個分支,稱為隨機圖理論,是圖論結果的豐富來源。
The introduction of probabilistic methods in graph theory, especially in the study of Erds and Rényi of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as random graph theory, which has been a fruitful source of graph-theoretic results.
哥尼斯堡大橋問題
The Knigsberg Bridge problem
04
—
圖繪製 Graph drawing
圖通過為每個頂點畫一個點或圓來直觀地表示，如果兩個頂點由一條邊連接，則在它們之間畫一條弧。
如果圖形是定向的，則通過畫一個箭頭來指示方向。
Graphs are represented visually by drawing a dot or circle for every vertex, and drawing an arc between two vertices if they are connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow.
圖繪製不應該與圖本身(抽象的、非可視的結構)相混淆，因為有幾種方法可以構造圖繪製。重要的是哪些頂點與哪些頂點之間是由多少條邊連接起來的，而不是確切的布局。
在實踐中，通常很難確定兩幅圖是否代表相同的圖。
根據問題域的不同，有些布局可能比其他布局更適合、更容易理解。
A graph drawing should not be confused with the graph itself (the abstract, non-visual structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout.
In practice it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.
圖特的開創性工作對圖形學產生了巨大的影響。
在其他成就中，他介紹了使用線性代數方法來獲得圖繪製。
The pioneering work of W. T. Tutte was very influential in the subject of graph drawing. Among other achievements, he introduced the use of linear algebraic methods to obtain graph drawings.
圖的繪製也可以說包含了處理交叉數及其各種推廣的問題。
圖的交點數是圖在平面上的繪圖所必須包含的邊之間交點的最小數目。
對於平面圖，根據定義，交叉數為零。
Graph drawing also can be said to encompass problems that deal with the crossing number and its various generalizations. The crossing number of a graph is the minimum number of intersections between edges that a drawing of the graph in the plane must contain. For a planar graph, the crossing number is zero by definition.
還研究了平面以外表面的繪圖。
Drawings on surfaces other than the plane are also studied.
05
—
圖論的數據結構 Graph-theoretic data structures
在計算機系統中存儲圖形有不同的方法。所使用的數據結構取決於圖形結構和用於操作圖形的算法。理論上可以區分列表結構和矩陣結構，但在具體應用中，最好的結構往往是兩者的結合。
對於稀疏圖，列表結構通常是首選的，因為它們的內存需求更小。
另一方面，矩陣結構為一些應用程式提供了更快的訪問速度，但是會消耗大量的內存。
There are different ways to store graphs in a computer system. The data structure used depends on both the graph structure and the algorithm used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both.
List structures are often preferred for sparse graphs as they have smaller memory requirements. Matrix structures on the other hand provide faster access for some applications but can consume huge amounts of memory.
列表結構包括關聯列表、頂點對數組和鄰接列表，鄰接列表分別列出每個頂點的鄰居:與關聯列表非常相似，每個頂點都有一個與之相鄰的頂點列表。
List structures include the incidence list, an array of pairs of vertices, and the adjacency list, which separately lists the neighbors of each vertex: Much like the incidence list, each vertex has a list of which vertices it is adjacent to.
矩陣結構包括關聯矩陣，一個0和1的矩陣，其行代表頂點，其列代表邊，以及鄰接矩陣，其中行和列都由頂點索引。在這兩種情況下，1表示兩個相鄰的對象，0表示兩個不相鄰的對象。
拉普拉斯矩陣是鄰接矩陣的一種改進形式，它包含了關於頂點度數的信息，在一些計算中很有用，比如圖的生成樹數的基爾霍夫定理。
與鄰接矩陣一樣，距離矩陣的行和列都以頂點為索引，但它在每個單元格中不包含0或1，而是包含兩個頂點之間最短路徑的長度。
Matrix structures include the incidence matrix, a matrix of 0's and 1's whose rows represent vertices and whose columns represent edges, and the adjacency matrix, in which both the rows and columns are indexed by vertices. In both cases a 1 indicates two adjacent objects and a 0 indicates two non-adjacent objects.
The Laplacian matrix is a modified form of the adjacency matrix that incorporates information about the degrees of the vertices, and is useful in some calculations such as Kirchhoff's theorem on the number of spanning trees of a graph.
The distance matrix, like the adjacency matrix, has both its rows and columns indexed by vertices, but rather than containing a 0 or a 1 in each cell it contains the length of a shortest path between two vertices.
06
—
圖論中的問題 Problems in graph theory
枚舉 Enumeration
有大量關於圖形枚舉的文獻:計算滿足指定條件的圖形的問題。
其中一些作品是在Harary和Palmer(1973)中發現的。
There is a large literature on graphical enumeration: the problem of counting graphs meeting specified conditions. Some of this work is found in Harary and Palmer (1973).
子圖、誘導子圖和餘子圖 Subgraphs, induced subgraphs, and minors
一個常見的問題，稱為子圖同構問題，是在給定的圖中找到一個固定的圖作為子圖。對這個問題感興趣的一個原因是，許多圖的屬性對於子圖來說是可遺傳的，這意味著若且唯若所有子圖都具有該屬性時，圖才具有該屬性。不幸的是，尋找某一類的極大子圖通常是一個np完全問題。例如:
A common problem, called the subgraph isomorphism problem, is finding a fixed graph as a subgraph in a given graph. One reason to be interested in such a question is that many graph properties are hereditary for subgraphs, which means that a graph has the property if and only if all subgraphs have it too.
Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem. For example:
尋找最大的完整子圖稱為團問題(NP-complete)。Finding the largest complete subgraph is called the clique problem (NP-complete).一個類似的問題是在給定的圖中尋找誘導子圖。
同樣，對於誘導子圖，一些重要的圖性質是遺傳的，這意味著一個圖具有一個性質，若且唯若所有的誘導子圖都具有這個性質。
尋找一類極大導子圖通常也是np完備的。
例如:
A similar problem is finding induced subgraphs in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example:
尋找最大的無邊緣誘導子圖或獨立集稱為獨立集問題(np -完全問題)。Finding the largest edgeless induced subgraph or independent set is called the independent set problem (NP-complete).還有一個這樣的問題，小包容問題，就是找到一個固定的圖作為一個給定圖的子圖。一個圖的次或次收縮是指通過取一個子圖並收縮一些(或不收縮一些)邊而得到的任何圖。許多圖屬性是可遺傳的，這意味著一個圖具有一個屬性，若且唯若所有的子圖都具有該屬性時。例如，華格納定理說:
Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. A minor or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. For example, Wagner's Theorem states:
如果一個圖既不包含完全二部圖K3,3(參見三村舍問題)，也不包含完全圖K5，那麼這個圖就是平面的。A graph is planar if it contains as a minor neither the complete bipartite graph K3,3 (see the Three-cottage problem) nor the complete graph K5.一個類似的問題，細分包容問題，是找到一個固定的圖作為一個給定圖的細分。圖的細分或同胚是通過細分一些(或沒有)邊而得到的任何圖。細分包含關係到圖的屬性，如平面性。例如，庫拉託夫斯基定理說:
A similar problem, the subdivision containment problem, is to find a fixed graph as a subdivision of a given graph. A subdivision or homeomorphism of a graph is any graph obtained by subdividing some (or no) edges. Subdivision containment is related to graph properties such as planarity. For example, Kuratowski's Theorem states:
如果一個圖既不包含完全的二部圖K3,3，也不包含完全的圖K5，那麼這個圖就是平面的。A graph is planar if it contains as a subdivision neither the complete bipartite graph K3,3 nor the complete graph K5.細分遏制的另一個問題是Kelmans-Seymour猜想:
Another problem in subdivision containment is Kelmans-Seymour conjecture:
每一個非平面的五頂點連通圖都包含一個五頂點完全圖K5的細分。Every 5-vertex-connected graph that is not planar contains a subdivision of the 5-vertex complete graph K5.另一類問題與圖的不同種類和一般化程度由它們的點刪除子圖所決定有關。
例如:
Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their point-deleted subgraphs. For example:
重建猜想The reconstruction conjecture圖著色 Graph coloring
很多問題都與著色圖形的各種方式有關，例如:
Many problems have to do with various ways of coloring graphs, for example:
四色定理 Four-color theorem強完全圖定理 Strong perfect graph theoremErds-Faber-Lovasz猜想(未解決)Erds–Faber–Lovász conjecture (unsolved)全著色猜想，也稱貝扎德猜想(未解決)Total coloring conjecture, also called Behzad's conjecture (unsolved)列表著色猜想(未解決)List coloring conjecture (unsolved)Hadwiger猜想(圖論)((未解決)Hadwiger conjecture (graph theory) (unsolved)包容和統一 Subsumption and unification
約束建模理論關注由偏序相關的有向圖族。在這些應用程式中，圖是按特異性排序的，這意味著更有約束的圖(更具體，因此包含更多的信息)被更一般的圖所包含。圖之間的操作包括評估兩個圖(如果有的話)之間包含關係的方向，以及計算圖的統一。
兩個參數圖的統一被定義為與輸入(即包含輸入的所有信息)一致的最一般的圖(或其計算)，如果這樣一個圖存在的話;有效的統一算法是已知的。
Constraint modeling theories concern families of directed graphs related by a partial order. In these applications, graphs are ordered by specificity, meaning that more constrained graphs—which are more specific and thus contain a greater amount of information—are subsumed by those that are more general. Operations between graphs include evaluating the direction of a subsumption relationship between two graphs, if any, and computing graph unification.
The unification of two argument graphs is defined as the most general graph (or the computation thereof) that is consistent with (i.e. contains all of the information in) the inputs, if such a graph exists; efficient unification algorithms are known.
對於嚴格組合的約束框架，圖的統一就是充分的可滿足性和組合函數。
著名的應用包括自動定理證明和建模語言結構的闡述。
For constraint frameworks which are strictly compositional, graph unification is the sufficient satisfiability and combination function. Well-known applications include automatic theorem proving and modeling the elaboration of linguistic structure.
路線問題 Route problems
哈密爾頓路徑問題 Hamiltonian path problem最小生成樹 Minimum spanning tree路線檢查問題(亦稱「中國郵差問題」) Route inspection problem (also called the "Chinese postman problem")柯尼斯堡七橋問題 Seven bridges of Knigsberg最短路徑問題 Shortest path pro斯坦納樹 Steiner treeThree-cottage問題 Three-cottage problem旅行商問題(NP-hard) Traveling salesman problem (NP-hard)網絡流 Network flow
有很多問題出現，特別是在應用中涉及到網絡中的各種流的概念，例如:
There are numerous problems arising especially from applications that have to do with various notions of flows in networks, for example:
最大流最小割定理 Max flow min cut theorem可見性問題 Visibility problems
博物館的保護問題 Museum guard problem覆蓋問題 Covering problems
圖中覆蓋問題是求子圖問題的具體實例，它們往往與團問題或獨立集問題密切相關。
Covering problems in graphs are specific instances of subgraph-finding problems, and they tend to be closely related to the clique problem or the independent set problem.
集合覆蓋問題 Set cover problem頂點覆蓋問題 Vertex cover problem分解問題 Decomposition problems
分解，定義為對一個圖的邊緣集進行分區(分區的每個部分的邊緣都有儘可能多的頂點)，有各種各樣的問題。通常，需要將一個圖分解成與一個固定圖同構的子圖;例如，將一個完全圖分解成哈密頓循環。
其他問題指定了一個圖族，其中一個給定的圖族應該被分解，例如，一個循環族，或者把一個完整的圖Kn分解成n - 1個指定的樹，分別有1、2、3、…、n - 1條邊。
Decomposition, defined as partitioning the edge set of a graph (with as many vertices as necessary accompanying the edges of each part of the partition), has a wide variety of question. Often, it is required to decompose a graph into subgraphs isomorphic to a fixed graph; for instance, decomposing a complete graph into Hamiltonian cycles.
Other problems specify a family of graphs into which a given graph should be decomposed, for instance, a family of cycles, or decomposing a complete graph Kn into n 1 specified trees having, respectively, 1, 2, 3, …, n 1 edges.
已經研究過的一些具體分解問題包括:
Some specific decomposition problems that have been studied include:
喬木性，分解成儘可能少的森林Arboricity, a decomposition into as few forests as possible循環兩次復蓋，分解成一個循環集合，每邊復蓋兩次Cycle double cover, a decomposition into a collection of cycles covering each edge exactly twice邊著色，分解成儘可能少的配色Edge coloring, a decomposition into as few matchings as possible圖因式分解，將一個正則圖分解成給定度的正則子圖Graph factorization, a decomposition of a regular graph into regular subgraphs of given degrees圖類 Graph classes
許多問題涉及到描述各種圖類的成員。以下是這類問題的一些例子:
Many problems involve characterizing the members of various classes of graphs. Some examples of such questions are below:
枚舉類的成員Enumerating the members of a class用禁止的子結構來描述一個類Characterizing a class in terms of forbidden substructures確定類之間的關係(例如，圖的一個屬性是否意味著另一個屬性)Ascertaining relationships among classes (e.g. does one property of graphs imply another)尋找有效的算法來決定一個類的成員Finding efficient algorithms to decide membership in a class查找類成員的表示形式Finding representations for members of a class