Function Repository Resource:

TournamentGraphQ

Return True if a graph is a tournament

Contributed by: Alejandra Ortiz Duran

ResourceFunction["TournamentGraphQ"][g]

yields True if the graph g is a Tournament, and False otherwise.

Details

A tournament is a directed graph, with neither self-loops nor multi-edges, in which there is exactly one directed edge joining each pair of distinct nodes.

ResourceFunction["TournamentGraphQ"] is intended for directed graphs. It returns False for other graph types.

Examples

Basic Examples (2)

Test whether a graph is a tournament:

In[1]:=

$ResourceFunction["TournamentGraphQ"][\!$\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4}, {{{2, 1}, {3, 1}, {1, 4}, {3, 2}, {2, 4}, {4, 3}}, Null}, {GraphLayout -> {"Dimension" -> 2, "VertexLayout" -> "StarEmbedding"}}]]}, TagBox[GraphicsGroupBox[ GraphicsComplexBox[{{0., 0.}, { 0.8660254037844389, -0.5000000000000012}, { 1.8369701987210297`*^-16, 1.}, {-0.8660254037844386, -0.49999999999999917`}}, { {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[Medium], ArrowBox[{{1, 4}, {2, 1}, {2, 4}, {3, 1}, {3, 2}, {4, 3}}, 0.020399597244776413`]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.020399597244776413], DiskBox[2, 0.020399597244776413], DiskBox[3, 0.020399597244776413], DiskBox[4, 0.020399597244776413]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None]$]$

Out[1]=

Test whether a larger graph is a tournament:

In[2]:=

Out[2]=

In[3]:=

Out[3]=

Scope (6)

Works with undirected graphs:

In[4]:=

$ResourceFunction["TournamentGraphQ"][\!$\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4}, {Null, SparseArray[ Automatic, {4, 4}, 0, {1, {{0, 3, 6, 9, 12}, {{2}, {3}, {4}, {1}, {3}, {4}, { 1}, {2}, {4}, {1}, {2}, {3}}}, Pattern}]}, {GraphLayout -> "StarEmbedding"}]]}, TagBox[GraphicsGroupBox[ GraphicsComplexBox[{{0., 0.}, { 0.8660254037844389, -0.5000000000000012}, { 1.8369701987210297`*^-16, 1.}, {-0.8660254037844386, -0.49999999999999917`}}, { {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[0.], ArrowBox[{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}, 0.020399597244776413`]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.020399597244776413], DiskBox[2, 0.020399597244776413], DiskBox[3, 0.020399597244776413], DiskBox[4, 0.020399597244776413]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None]$]$

Out[4]=

Directed graphs:

In[5]:=

$ResourceFunction["TournamentGraphQ"][\!$\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4}, {{{2, 1}, {3, 1}, {1, 4}, {3, 2}, {2, 4}, {4, 3}}, Null}, {FormatType -> TraditionalForm, GraphLayout -> {"Dimension" -> 2, "VertexLayout" -> "StarEmbedding"}}]]}, TagBox[GraphicsGroupBox[ GraphicsComplexBox[{{0., 0.}, { 0.8660254037844389, -0.5000000000000012}, { 1.8369701987210297`*^-16, 1.}, {-0.8660254037844386, -0.49999999999999917`}}, { {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[Medium], ArrowBox[{{1, 4}, {2, 1}, {2, 4}, {3, 1}, {3, 2}, {4, 3}}, 0.020399597244776413`]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.020399597244776413], DiskBox[2, 0.020399597244776413], DiskBox[3, 0.020399597244776413], DiskBox[4, 0.020399597244776413]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None]$]$

Out[5]=

Weighted graphs:

In[6]:=

$ResourceFunction["TournamentGraphQ"][\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5}, {Null, SparseArray[ Automatic, {5, 5}, 0, {1, {{0, 3, 6, 8, 9, 10}, {{2}, {3}, {4}, {2}, {3}, { 5}, {4}, {5}, {5}, {5}}}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}]}, {FormatType -> TraditionalForm, GraphLayout -> {"Dimension" -> 2}, VertexLabels -> { Placed[Automatic, Center]}, VertexSize -> {0.25}, VertexStyle -> { GrayLevel[1]}}]]}, TagBox[GraphicsGroupBox[{ {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[0.], ArrowBox[{{0., 0.012484330888018924`}, { 0.011333771416589089`, 1.1666638939968836`}}, 0.10192290483023064`], ArrowBox[{{0., 0.012484330888018924`}, {0.5818822250328072, 0.5841484109973273}}, 0.10192290483023064`], ArrowBox[{{0., 0.012484330888018924`}, {1.1541843168018768`, 0.}}, 0.10192290483023064`], ArrowBox[ BezierCurveBox[{{0.011333771416589089`, 1.1666638939968836`}, {-0.18684105756379346`, 1.0962815719756591`}, {-0.3663390917212296, 1.1988433261781792`}, {-0.4132538528198191, 1.3309407689787274`}, {-0.14439391571122775`, 1.5944610769823941`}, {-0.013264036975934812`, 1.544906217419994}, {0.08567681402759109, 1.3633871669206583`}, {0.011333771416589089`, 1.1666638939968836`}}, SplineDegree->7], 0.10192290483023064`], ArrowBox[{{0.011333771416589089`, 1.1666638939968836`}, { 0.5818822250328072, 0.5841484109973273}}, 0.10192290483023064`], ArrowBox[{{0.011333771416589089`, 1.1666638939968836`}, { 1.1666848480058034`, 1.1548334540590575`}}, 0.10192290483023064`], ArrowBox[{{0.5818822250328072, 0.5841484109973273}, { 1.1541843168018768`, 0.}}, 0.10192290483023064`], ArrowBox[{{0.5818822250328072, 0.5841484109973273}, { 1.1666848480058034`, 1.1548334540590575`}}, 0.10192290483023064`], ArrowBox[{{1.1541843168018768`, 0.}, {1.1666848480058034`, 1.1548334540590575`}}, 0.10192290483023064`], ArrowBox[ BezierCurveBox[{{1.1666848480058034`, 1.1548334540590575`}, {1.096428457927411, 1.3530529650328658`}, {1.1990740340904533`, 1.532488387080747}, {1.3311868766939918`, 1.579333895788655}, {1.5945558474459913`, 1.3103582119248316`}, {1.5449381846459758`, 1.1792613301726174`}, {1.3633806566239384`, 1.0804177719107293`}, {1.1666848480058034`, 1.1548334540590575`}}, SplineDegree->7], 0.10192290483023064`]}, {GrayLevel[1], EdgeForm[{GrayLevel[0], Opacity[ 0.7]}], { DiskBox[{0., 0.012484330888018924`}, 0.10192290483023064], InsetBox["1", {0., 0.012484330888018924}, BaseStyle->"Graphics"]}, { DiskBox[{0.011333771416589089`, 1.1666638939968836`}, 0.10192290483023064], InsetBox["2", {0.011333771416589089, 1.1666638939968836}, BaseStyle->"Graphics"]}, { DiskBox[{0.5818822250328072, 0.5841484109973273}, 0.10192290483023064], InsetBox["3", {0.5818822250328072, 0.5841484109973273}, BaseStyle->"Graphics"]}, { DiskBox[{1.1541843168018768`, 0.}, 0.10192290483023064], InsetBox["4", {1.1541843168018768, 0.}, BaseStyle->"Graphics"]}, { DiskBox[{1.1666848480058034`, 1.1548334540590575`}, 0.10192290483023064], InsetBox["5", {1.1666848480058034, 1.1548334540590575}, BaseStyle->"Graphics"]}}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None, ImageSize->{131.4000000000001, Automatic}]\)]$

Out[6]=

Multigraphs:

In[7]:=

$ResourceFunction["TournamentGraphQ"][\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5}, {Null, SparseArray[ Automatic, {5, 5}, 0, {1, {{0, 3, 6, 8, 9, 10}, {{2}, {3}, {4}, {2}, {3}, { 5}, {4}, {5}, {5}, {5}}}, {2, 1, 1, 1, 1, 1, 1, 1, 2, 1}}]}, {GraphLayout -> {"Dimension" -> 2}, ImageSize -> {131.4000000000001, Automatic}, VertexLabels -> { Placed[Automatic, Center]}, VertexSize -> {0.25}, VertexStyle -> { GrayLevel[1]}}]]}, TagBox[GraphicsGroupBox[{ {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[0.], ArrowBox[ BezierCurveBox[{{0., 0.012484330888018924`}, {-0.18412726403280927`, 0.5914378462825931}, {0.011333771416589089`, 1.1666638939968836`}}], 0.10192290483023064`], ArrowBox[ BezierCurveBox[{{0., 0.012484330888018924`}, { 0.195461035449399, 0.5877103786023026}, { 0.011333771416589089`, 1.1666638939968836`}}], 0.10192290483023064`], ArrowBox[{{0., 0.012484330888018924`}, {0.5818822250328072, 0.5841484109973273}}, 0.10192290483023064`], ArrowBox[{{0., 0.012484330888018924`}, {1.1541843168018768`, 0.}}, 0.10192290483023064`], ArrowBox[ BezierCurveBox[{{0.011333771416589089`, 1.1666638939968836`}, {-0.18684105756379346`, 1.0962815719756591`}, {-0.3663390917212296, 1.1988433261781792`}, {-0.4132538528198191, 1.3309407689787274`}, {-0.14439391571122775`, 1.5944610769823941`}, {-0.013264036975934812`, 1.544906217419994}, {0.08567681402759109, 1.3633871669206583`}, {0.011333771416589089`, 1.1666638939968836`}}, SplineDegree->7], 0.10192290483023064`], ArrowBox[{{0.011333771416589089`, 1.1666638939968836`}, { 0.5818822250328072, 0.5841484109973273}}, 0.10192290483023064`], ArrowBox[{{0.011333771416589089`, 1.1666638939968836`}, { 1.1666848480058034`, 1.1548334540590575`}}, 0.10192290483023064`], ArrowBox[{{0.5818822250328072, 0.5841484109973273}, { 1.1541843168018768`, 0.}}, 0.10192290483023064`], ArrowBox[{{0.5818822250328072, 0.5841484109973273}, { 1.1666848480058034`, 1.1548334540590575`}}, 0.10192290483023064`], ArrowBox[ BezierCurveBox[{{1.1541843168018768`, 0.}, { 0.9705329063463092, 0.5794723237208922}, { 1.1666848480058034`, 1.1548334540590575`}}], 0.10192290483023064`], ArrowBox[ BezierCurveBox[{{1.1541843168018768`, 0.}, { 1.3503362584613736`, 0.5753611303381693}, { 1.1666848480058034`, 1.1548334540590575`}}], 0.10192290483023064`], ArrowBox[ BezierCurveBox[{{1.1666848480058034`, 1.1548334540590575`}, {1.096428457927411, 1.3530529650328658`}, {1.1990740340904533`, 1.532488387080747}, {1.3311868766939918`, 1.579333895788655}, {1.5945558474459913`, 1.3103582119248316`}, {1.5449381846459758`, 1.1792613301726174`}, {1.3633806566239384`, 1.0804177719107293`}, {1.1666848480058034`, 1.1548334540590575`}}, SplineDegree->7], 0.10192290483023064`]}, {GrayLevel[1], EdgeForm[{GrayLevel[0], Opacity[ 0.7]}], { DiskBox[{0., 0.012484330888018924`}, 0.10192290483023064], InsetBox["1", {0., 0.012484330888018924}, BaseStyle->"Graphics"]}, { DiskBox[{0.011333771416589089`, 1.1666638939968836`}, 0.10192290483023064], InsetBox["2", {0.011333771416589089, 1.1666638939968836}, BaseStyle->"Graphics"]}, { DiskBox[{0.5818822250328072, 0.5841484109973273}, 0.10192290483023064], InsetBox["3", {0.5818822250328072, 0.5841484109973273}, BaseStyle->"Graphics"]}, { DiskBox[{1.1541843168018768`, 0.}, 0.10192290483023064], InsetBox["4", {1.1541843168018768, 0.}, BaseStyle->"Graphics"]}, { DiskBox[{1.1666848480058034`, 1.1548334540590575`}, 0.10192290483023064], InsetBox["5", {1.1666848480058034, 1.1548334540590575}, BaseStyle->"Graphics"]}}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None, ImageSize->{131.4000000000001, Automatic}]\)]$

Out[7]=

Mixed graphs:

In[8]:=

$ResourceFunction["TournamentGraphQ"][\!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{2, 1, 3, 4, 5}, {{{1, 2}, {4, 2}, {3, 1}, {3, 5}, {5, 5}}, {{3, 2}, {1, 1}, {5, 1}, {5, 4}}}, {FormatType -> TraditionalForm, GraphLayout -> {"Dimension" -> 2}, VertexLabels -> { Placed[Automatic, Center]}, VertexSize -> {0.2}, VertexStyle -> { GrayLevel[1]}}]]}, TagBox[GraphicsGroupBox[{ {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[Medium], {Arrowheads[0.], ArrowBox[ BezierCurveBox[{{1.7750956636961295`, 0.13226206424409698`}, {1.966185455332654, 0.22007793074812088`}, {2.154132967190708, 0.1340028601544194}, {2.2126817457067816`, 0.0066437403350446955`}, { 1.968508088505095, -0.27987041008990765`}, { 1.8334766867831747`, -0.2422562449934525}, { 1.718689729212581, -0.07033434597232444}, { 1.7750956636961295`, 0.13226206424409698`}}, SplineDegree->7], 0.07142150267772777]}, {Arrowheads[0.], ArrowBox[{{1.7750956636961295`, 0.13226206424409698`}, { 0.943188822949299, 0.}}, 0.07142150267772777]}, ArrowBox[{{1.7750956636961295`, 0.13226206424409698`}, { 0.9446927018534159, 0.979176716752343}}, 0.07142150267772777], {Arrowheads[0.], ArrowBox[{{0.9446927018534159, 0.979176716752343}, { 1.7739785995788884`, 0.8464762174518206}}, 0.07142150267772777]}, ArrowBox[{{1.7739785995788884`, 0.8464762174518206}, { 1.7750956636961295`, 0.13226206424409698`}}, 0.07142150267772777], ArrowBox[{{1.7739785995788884`, 0.8464762174518206}, { 0.943188822949299, 0.}}, 0.07142150267772777], {Arrowheads[0.], ArrowBox[{{0., 0.4896215582219036}, {0.943188822949299, 0.}}, 0.07142150267772777]}, ArrowBox[{{0., 0.4896215582219036}, {0.9446927018534159, 0.979176716752343}}, 0.07142150267772777], ArrowBox[ BezierCurveBox[{{0.943188822949299, 0.}, { 1.1211614620882508`, -0.12504457378621806`}, { 1.1394455650204758`, -0.32804828408198256`}, { 1.0602355701475654`, -0.44122719423721557`}, { 0.6928479934285716, -0.38172090202006825`}, { 0.6534140914385866, -0.2493250698895323}, { 0.7348438308049134, -0.06247215350711399}, { 0.943188822949299, 0.}}, SplineDegree->7], 0.07142150267772777]}, {GrayLevel[1], EdgeForm[{GrayLevel[0], Opacity[ 0.7]}], { DiskBox[{1.7750956636961295`, 0.13226206424409698`}, 0.07142150267772777], InsetBox["2", {1.7750956636961295, 0.13226206424409698}, BaseStyle->"Graphics"]}, { DiskBox[{0.9446927018534159, 0.979176716752343}, 0.07142150267772777], InsetBox["1", {0.9446927018534159, 0.979176716752343}, BaseStyle->"Graphics"]}, { DiskBox[{1.7739785995788884`, 0.8464762174518206}, 0.07142150267772777], InsetBox["3", {1.7739785995788884, 0.8464762174518206}, BaseStyle->"Graphics"]}, { DiskBox[{0., 0.4896215582219036}, 0.07142150267772777], InsetBox["4", {0., 0.4896215582219036}, BaseStyle->"Graphics"]}, { DiskBox[{0.943188822949299, 0.}, 0.07142150267772777], InsetBox["5", {0.943188822949299, 0.}, BaseStyle->"Graphics"]}}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None, ImageSize->{189.5999999999999, Automatic}]\)]$

Out[8]=

A non-tournament graph:

In[9]:=

$g = Graph[{2 \[DirectedEdge] 1, 3 \[DirectedEdge] 1, 1 \[DirectedEdge] 4, 3 \[DirectedEdge] 2, 2 \[DirectedEdge] 4, 4 \[DirectedEdge] 3, 3 \[DirectedEdge] 4}]$