Editing Glossary of graph theory (section)

==A==
{{glossary}}

{{term|absorbing}}
{{defn|An absorbing set <math>A</math> of a directed graph <math>G</math> is a set of vertices such that for any vertex <math>v \in G \setminus A</math>, there is an edge from <math>v</math> towards a vertex of <math>A</math>.}}

{{term|achromatic}}
{{defn|The [[achromatic number]] of a graph is the maximum number of colors in a complete coloring.<ref>{{citation|last1=Farber|first1=M.|last2=Hahn|first2=G.|last3=Hell|first3=P.|author3-link=Pavol Hell|last4=Miller|first4=D. J.|title=Concerning the achromatic number of graphs|journal=Journal of Combinatorial Theory, Series B|volume=40|issue=1|year=1986|pages=21–39|doi=10.1016/0095-8956(86)90062-6|doi-access=free}}.</ref>}}

{{term|acyclic}}
{{defn|no=1|A graph is acyclic if it has no cycles. An undirected acyclic graph is the same thing as a [[Tree (graph theory)|forest]]. An acyclic directed graph, which is a digraph without directed cycles, is often called a [[directed acyclic graph]], especially in computer science.<ref name="clrs">{{citation|title=Introduction to Algorithms|year=2001|publisher=MIT Press and McGraw-Hill|first1=Thomas H.|last1=Cormen|author1-link=Thomas H. Cormen|first2=Charles E.|last2=Leiserson|author2-link=Charles E. Leiserson|first3=Ronald L.|last3=Rivest|author3-link=Ron Rivest|first4=Clifford|last4=Stein|author4-link=Clifford Stein|chapter=B.4 Graphs|pages=1080–1084|edition=2|title-link=Introduction to Algorithms}}.</ref>}}
{{defn|no=2|An [[acyclic coloring]] of an undirected graph is a proper coloring in which every two color classes induce a forest.<ref>{{Citation | doi = 10.1007/BF02764716 | doi-access=free | last1 = Grünbaum | first1 = B. | author-link = Branko Grünbaum | year = 1973 | title = Acyclic colorings of planar graphs | journal = [[Israel Journal of Mathematics]] | volume = 14 | issue = 4| pages = 390–408}}.</ref>}}

{{term|adjacency matrix}}
{{defn|The [[adjacency matrix]] of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row {{mvar|i}} and column {{mvar|j}} when vertices {{mvar|i}} and {{mvar|j}} are adjacent, and a zero otherwise.<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, p.&nbsp;529.</ref>}}

{{term|adjacent}}
{{defn|no=1|The relation between two vertices that are both endpoints of the same edge.<ref name="clrs"/>}}
{{defn|no=2|The relation between two distinct edges that share an end vertex.<ref name="diestel">{{citation|title=Graph Theory|year=2017|publisher=Springer-Verlag|location=Berlin, New York|first=Reinhard|last=Diestel|chapter=1.1 Graphs|series=Graduate Texts in Mathematics|volume=173|pages=3|edition=5th|doi=10.1007/978-3-662-53622-3|isbn=978-3-662-53621-6}}.</ref>}}

{{term|alpha|''&alpha;''}}
{{defn|For a graph {{mvar|G}}, {{math|''&alpha;''(''G'')}} (using the Greek letter alpha) is its independence number (see {{gli|independent}}), and {{math|''&alpha;''′(''G'')}} is its matching number (see {{gli|matching}}).}}

{{term|alternating}}
{{defn|In a graph with a matching, an alternating path is a path whose edges alternate between matched and unmatched edges. An alternating cycle is, similarly, a cycle whose edges alternate between matched and unmatched edges. An augmenting path is an alternating path that starts and ends at unsaturated vertices. A larger matching can be found as the [[symmetric difference]] of the matching and the augmenting path; a matching is maximum if and only if it has no augmenting path.}}

{{term|antichain}}
{{defn|In a [[directed acyclic graph]], a subset {{mvar|S}} of vertices that are pairwise incomparable, i.e., for any <math>x \leq y </math> in {{mvar|S}}, there is no directed path from {{mvar|x}} to {{mvar|y}} or from {{mvar|y}} to {{mvar|x}}. Inspired by the notion of [[antichain]]s in [[partially ordered set]]s.}}

{{term|anti-edge}}
{{defn|Synonym for ''non-edge'', a pair of non-adjacent vertices.}}

{{term|anti-triangle}}
{{defn|A three-vertex independent set, the complement of a triangle.}}

{{term|apex}}
{{defn|no=1|An [[apex graph]] is a graph in which one vertex can be removed, leaving a {{gli|planar}} subgraph. The removed vertex is called the apex. A {{mvar|k}}-apex graph is a graph that can be made planar by the removal of {{mvar|k}} vertices.}}
{{defn|no=2|Synonym for [[universal vertex]], a vertex adjacent to all other vertices.}}

{{term|arborescence}}
{{defn|Synonym for a rooted and directed tree; see {{gli|tree}}.}}

{{term|arc}}
{{defn|See {{gli|edge}}.}}

{{term|arrow}}
{{defn|An [[ordered pair]] of {{gli|vertex|vertices}}, such as an {{gli|edge}} in a {{gli|directed graph}}. An arrow {{math|(''x'', ''y'')}} has a {{gli|tail}} {{math|''x''}}, a {{gli|head}} {{math|''y''}}, and a {{gli|direction}} {{math|from ''x'' to ''y''}}; {{math|''y''}} is said to be the {{gli|direct successor}} to {{math|''x''}} and {{math|''x''}} the {{gli|direct predecessor}} to {{math|''y''}}. The arrow {{math|(''y'', ''x'')}} is the {{gli|inverted arrow}} of the arrow {{math|(''x'', ''y'')}}.}}

{{term|articulation point|[[articulation point]]}}
{{defn|A {{gli|vertex}} in a {{gli|connected graph}} whose removal would {{gli|disconnect}} the graph. More generally, a vertex whose removal increases the number of {{gli|component}}s.}}

{{term|k-ary|-ary}}
{{defn|A [[K-ary tree|{{mvar|k}}-ary tree]] is a rooted tree in which every internal vertex has no more than {{mvar|k}} children. A 1-ary tree is just a path. A 2-ary tree is also called a [[binary tree]], although that term more properly refers to 2-ary trees in which the children of each node are distinguished as being left or right children (with at most one of each type).  A {{mvar|k}}-ary tree is said to be complete if every internal vertex has exactly {{mvar|k}} children.}}

{{term|augmenting}}
{{defn|A special type of alternating path; see {{gli|alternating}}.}}

{{term|automorphism}}
{{defn|A [[graph automorphism]] is a symmetry of a graph, an isomorphism from the graph to itself.}}

{{glossary end}}