Editing Rooted graph (section)

==Variations==
In [[topological graph theory]], the notion of a rooted graph may be extended to consider multiple vertices or multiple edges as roots. The former are sometimes called vertex-rooted graphs in order to distinguish them from edge-rooted graphs in this context.<ref>{{Citation|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|first3=Ping|last3=Zhang|author3-link=Ping Zhang (graph theorist)|title=Handbook of Graph Theory|edition=2nd|year=2013|publisher=CRC Press|isbn=978-1-4398-8018-0|pages=764–765}}</ref> Graphs with multiple nodes designated as roots are also of some interest in [[combinatorics]], in the area of [[random graphs]].<ref>{{citation|first=Joel|last=Spencer|authorlink=Joel Spencer|title=The Strange Logic of Random Graphs|title-link= The Strange Logic of Random Graphs |year=2001|publisher=Springer Science & Business Media|isbn=978-3-540-41654-8|at=chapter 4}}</ref> These graphs are also called '''multiply rooted graphs'''.<ref>{{harvtxt|Harary|1955|page=455}}.</ref>

The terms '''rooted [[directed graph]]''' or '''rooted digraph''' also see variation in definitions. The obvious transplant is to consider a digraph rooted by identifying a particular node as root.<ref name="greedintro">{{Citation|last1=Björner|first1=Anders|last2=Ziegler|first2=Günter M.|authorlink2=Günter M. Ziegler|authorlink1=Anders Björner|chapter=8. Introduction to greedoids|series=Encyclopedia of Mathematics and its Applications|volume=40|editor-last=White|editor-first=Neil|publisher=Cambridge University Press|location=Cambridge|year=1992|isbn=0-521-38165-7 |pages=[https://archive.org/details/matroidapplicati0000unse/page/284 284–357] |doi=10.1017/CBO9780511662041.009 |mr=1165537 |zbl=0772.05026 |title=Matroid Applications |url=https://archive.org/details/matroidapplicati0000unse/page/284 |chapter-url=https://www.mi.fu-berlin.de/math/groups/discgeom/ziegler/Preprintfiles/006PREPRINT.pdf#page=40 |quote=In this context a rooted digraph Δ = (''V'',''E'',''r'') is called ''connected'' (or ''1-connected'') if there is a directed path from the root to every vertex.}} See in particular p.&nbsp;307.</ref><ref name="poly">{{citation
 | last1 = Gordon | first1 = Gary
 | last2 = McMahon | first2 = Elizabeth
 | doi = 10.1090/s0002-9939-1989-0967486-0 | doi-access = free
 | journal = [[Proceedings of the American Mathematical Society]]
 | volume = 107 | issue = 2 | pages = 287 | date = February 1989
 | title = A greedoid polynomial which distinguishes rooted arborescences
 | citeseerx = 10.1.1.308.2526
 | url = https://webbox.lafayette.edu/~gordong/pubs/greedoid.pdf
 | quote = A rooted subdigraph ''F'' is a ''rooted arborescence'' if the root vertex ∗ is in ''F'' and, for every vertex ''v'' in ''F'', there is a unique directed path in ''F'' from ∗ to ''v''. Thus, rooted arborescences in digraphs correspond to rooted trees in undirected graphs.
 }}</ref> However, in [[computer science]], these terms commonly refer to a narrower notion; namely, a rooted directed graph is a digraph with a distinguished node ''r'', such that there is a directed path from ''r'' to any node other than ''r''.<ref>{{citation | doi = 10.1007/978-1-4684-5511-3_8 | title=Fast Parallel Algorithms for Reducible Flow Graphs | journal=Concurrent Computations | date=1988 | pages=117–138 | first=Vijaya | last=Ramachandran | isbn=978-1-4684-5513-7 |quote=A ''rooted directed graph'' or a ''flow graph'' ''G'' = (''V'', ''A'', ''r'') is a  directed graph with a distinguished vertex ''r'' such that there is a directed path in ''G'' from ''r'' to every vertex ''v'' in {{nobr|''V'' − ''r''}}. }}. See in particular p.&nbsp;122.</ref><ref>{{citation | doi = 10.1016/S0166-218X(02)00471-7 | title=The forbidden minor characterization of line-search antimatroids of rooted digraphs | journal=Discrete Applied Mathematics | date=2003 | volume=131 | issue=2 | pages=523–533 | first1=Yoshio | last1=Okamoto |first2=Masataka |last2=Nakamura | doi-access=free | url=http://dopal.cs.uec.ac.jp/okamotoy/PDF/2003/rminorWEB.pdf | quote=A ''rooted'' digraph is a triple ''G''=(''V'',''E'',''r'')  where (''V'' ∪ {''r''}, ''E'') is a digraph and ''r'' is a specified vertex called the root such that there exists a path from ''r'' to every vertex of ''V''.}}. See in particular p.&nbsp;524.</ref><ref>{{citation |first=Abhinandan |last=Jain |title=Robot and Multibody Dynamics: Analysis and Algorithms |year=2010 |publisher=Springer Science & Business Media |isbn=978-1-4419-7267-5 |page=136 |quote=A '''rooted digraph''' is a connected digraph with a single root node that is the ancestor of every other node in the digraph. }}</ref><ref>{{citation
 | last1 = Chen | first1 = Xujin
 | last2 = Zang | first2 = Wenan
 | doi = 10.1007/s00453-005-1174-x
 | issue = 3
 | journal = Algorithmica
 | mr = 2199991
 | pages = 195–211
 | title = An efficient algorithm for finding maximum cycle packings in reducible flow graphs
 | volume = 44
 | year = 2006| hdl = 10722/48600
 | s2cid = 5235131
 | hdl-access = free
 }}</ref> Authors who give the more general definition may refer to graphs meeting the narrower definition as ''connected'' rooted digraphs<ref name="greedintro"/> or ''accessible'' rooted graphs (see {{alink|Set theory}}).

''[[The Art of Computer Programming]]'' defines rooted digraphs slightly more broadly, namely, a directed graph is called rooted if it has ''at least one'' node that can reach all the other nodes. Knuth notes that the notion thus defined is a sort of intermediate between the notions of [[strongly connected]] and [[Digraph (mathematics)#Digraph connectivity|connected digraph]].<ref>{{citation |last=Knuth |first=Donald |authorlink=Donald Knuth |title=[[The Art of Computer Programming]] |volume=1 |edition=3rd |chapter=2.3.4.2. Oriented trees |year=1997 |publisher=Pearson Education |isbn=0-201-89683-4 |page=372 |quote=It is said to be rooted if there is at least one root, that is, at least one vertex ''R'' such that there is an oriented path from ''V'' to ''R'' for all ''V'' ≠ ''R''. }}</ref>