256:
by making two elements adjacent whenever they are comparable in the partial order. A transitive orientation, if one exists, can be found in linear time. However, testing whether the resulting orientation (or any given orientation) is actually transitive requires more time, as it is equivalent in
153:
Tournaments are in one-to-one correspondence with complete directed graphs (graphs in which there is a directed edge in one or both directions between every pair of distinct vertices). A complete directed graph can be converted to an oriented graph by removing every 2-cycle, and conversely an
213:. Every graph has an acyclic orientation; all acyclic orientations may be obtained by placing the vertices into a sequence, and then directing each edge from the earlier of its endpoints in the sequence to the later endpoint. The
58:
if none of its pairs of vertices is linked by two mutually symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of
570:
154:
oriented graph can be converted to a complete directed graph by adding a 2-cycle between every pair of vertices that are not endpoints of an edge; these correspondences are
287:
has the property that certain even-length cycles in the graph have an odd number of edges oriented in each of the two directions around the cycle. They always exist for
178:. The closely related totally cyclic orientations are orientations in which every edge belongs to at least one simple cycle. An orientation of an undirected graph
568:
Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre",
214:
146:
681:
499:
342:
183:
430:
334:
268:
of an undirected graph is an orientation in which each vertex has equal in-degree and out-degree. Eulerian orientations of
755:
654:
325:
86:
524:
479:
175:
162:
problem for complete digraphs. There is an explicit but complicated formula for the numbers in this sequence.
364:
Proc. 3rd Annual
Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987
475:
241:
210:
195:
102:
273:
258:
253:
199:
284:
249:
234:
206:
191:
98:
457:
367:
245:
171:
728:
709:
677:
495:
338:
159:
121:
669:
628:
540:
487:
447:
439:
39:
691:
640:
583:
554:
509:
411:
687:
636:
579:
550:
505:
425:
407:
304:
229:
colors. Acyclic orientations and totally cyclic orientations are related to each other by
658:
277:
222:
90:
43:
713:
386:
749:
614:
545:
292:
265:
217:
states that a graph has an acyclic orientation in which the longest path has at most
198:; disconnected graphs may have totally cyclic orientations, but only if they have no
428:(1939), "A theorem on graphs, with an application to a problem of traffic control",
732:
619:
399:
288:
31:
528:
486:, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42,
359:
230:
42:
is an assignment of a direction to each edge, turning the initial graph into a
491:
452:
269:
17:
737:
718:
597:
McConnell, R. M.; Spinrad, J. (1997), "Linear-time transitive orientation",
233:. An acyclic orientation with a single source and a single sink is called a
155:
632:
94:
673:
461:
139:
1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … (sequence
182:
is totally cyclic if and only if it is a strong orientation of every
443:
244:
is an orientation such that the resulting directed graph is its own
362:(1987), "The recovery of causal poly-trees from statistical data",
372:
194:
states that a graph has a strong orientation if and only if it is
617:(1996), "On the number of Eulerian orientations of a graph",
141:
324:
Diestel, Reinhard (2005), "1.10 Other notions of graphs",
158:. Therefore, the same sequence of numbers also solves the
291:, but not for certain other graphs. They are used in the
27:
Assigning directions to the edges of an undirected graph
248:. The graphs with transitive orientations are called
666:International Congress of Mathematicians. Vol. III
668:, Eur. Math. Soc., Zürich, pp. 963–984,
659:"A survey of Pfaffian orientations of graphs"
599:8th ACM-SIAM Symposium on Discrete Algorithms
571:Les Comptes rendus de l'Académie des sciences
402:; Palmer, Edgar M. (1973), "Formula 5.4.13",
8:
484:Sparsity: Graphs, Structures, and Algorithms
531:(1995), "Bipolar orientations revisited",
544:
451:
406:, New York: Academic Press, p. 133,
371:
389:, Douglas B. West, retrieved 2012-08-02.
387:Sumner's Universal Tournament Conjecture
316:
113:vertices contains every polytree with
7:
209:is an orientation that results in a
174:is an orientation that results in a
97:is an orientation of an undirected
221:vertices if and only if it can be
105:states that every tournament with
25:
431:The American Mathematical Monthly
295:for counting perfect matchings.
215:Gallai–Hasse–Roy–Vitaver theorem
54:A directed graph is called an
1:
252:; they may be defined from a
82:may be arrows of the graph).
546:10.1016/0166-218X(94)00085-R
533:Discrete Applied Mathematics
772:
525:Ossona de Mendez, Patrice
492:10.1007/978-3-642-27875-4
480:Ossona de Mendez, Patrice
482:(2012), "Theorem 3.13",
176:strongly connected graph
166:Constrained orientations
89:is an orientation of a
523:de Fraysseix, Hubert;
242:transitive orientation
211:directed acyclic graph
633:10.1007/s004539900057
404:Graphical Enumeration
274:statistical mechanics
259:matrix multiplication
254:partially ordered set
124:oriented graphs with
756:Graph theory objects
366:, pp. 222–228,
285:Pfaffian orientation
266:Eulerian orientation
250:comparability graphs
714:"Graph Orientation"
529:Rosenstiehl, Pierre
235:bipolar orientation
207:acyclic orientation
184:connected component
103:Sumner's conjecture
729:Weisstein, Eric W.
710:Weisstein, Eric W.
476:Nešetřil, Jaroslav
453:10338.dmlcz/101517
246:transitive closure
172:strong orientation
683:978-3-03719-022-7
501:978-3-642-27874-7
344:978-3-540-26182-7
276:in the theory of
160:graph enumeration
16:(Redirected from
763:
742:
741:
733:"Oriented Graph"
723:
722:
695:
694:
674:10.4171/022-3/47
663:
651:
645:
643:
627:(4–5): 402–414,
610:
604:
602:
601:, pp. 19–25
594:
588:
586:
565:
559:
557:
548:
539:(2–3): 157–179,
520:
514:
512:
472:
466:
464:
455:
422:
416:
414:
396:
390:
384:
378:
376:
375:
358:Rebane, George;
355:
349:
347:
333:(3rd ed.),
332:
321:
228:
220:
196:2-edge-connected
192:Robbins' theorem
189:
181:
144:
134:
127:
116:
112:
81:
69:
40:undirected graph
21:
771:
770:
766:
765:
764:
762:
761:
760:
746:
745:
727:
726:
708:
707:
704:
699:
698:
684:
661:
653:
652:
648:
612:
611:
607:
596:
595:
591:
567:
566:
562:
522:
521:
517:
502:
474:
473:
469:
444:10.2307/2303897
424:
423:
419:
398:
397:
393:
385:
381:
357:
356:
352:
345:
330:
323:
322:
318:
313:
305:Connex relation
301:
278:ice-type models
226:
218:
187:
179:
168:
140:
129:
125:
114:
106:
71:
59:
52:
50:Oriented graphs
28:
23:
22:
15:
12:
11:
5:
769:
767:
759:
758:
748:
747:
744:
743:
724:
703:
702:External links
700:
697:
696:
682:
646:
605:
589:
560:
515:
500:
467:
438:(5): 281–283,
426:Robbins, H. E.
417:
391:
379:
350:
343:
315:
314:
312:
309:
308:
307:
300:
297:
257:complexity to
231:planar duality
167:
164:
151:
150:
128:vertices (for
122:non-isomorphic
120:The number of
91:complete graph
56:oriented graph
51:
48:
44:directed graph
26:
24:
18:Oriented graph
14:
13:
10:
9:
6:
4:
3:
2:
768:
757:
754:
753:
751:
740:
739:
734:
730:
725:
721:
720:
715:
711:
706:
705:
701:
693:
689:
685:
679:
675:
671:
667:
660:
656:
655:Thomas, Robin
650:
647:
642:
638:
634:
630:
626:
622:
621:
616:
609:
606:
600:
593:
590:
585:
581:
578:: 1370–1371,
577:
573:
572:
564:
561:
556:
552:
547:
542:
538:
534:
530:
526:
519:
516:
511:
507:
503:
497:
493:
489:
485:
481:
477:
471:
468:
463:
459:
454:
449:
445:
441:
437:
433:
432:
427:
421:
418:
413:
409:
405:
401:
400:Harary, Frank
395:
392:
388:
383:
380:
374:
369:
365:
361:
354:
351:
346:
340:
336:
329:
328:
320:
317:
310:
306:
303:
302:
298:
296:
294:
293:FKT algorithm
290:
289:planar graphs
286:
281:
279:
275:
271:
267:
262:
260:
255:
251:
247:
243:
238:
236:
232:
225:with at most
224:
216:
212:
208:
203:
201:
197:
193:
185:
177:
173:
165:
163:
161:
157:
148:
143:
138:
137:
136:
132:
123:
118:
110:
104:
100:
96:
92:
88:
83:
79:
75:
67:
63:
57:
49:
47:
45:
41:
37:
33:
19:
736:
717:
665:
649:
624:
620:Algorithmica
618:
613:Mihail, M.;
608:
598:
592:
575:
569:
563:
536:
532:
518:
483:
470:
435:
429:
420:
403:
394:
382:
363:
360:Pearl, Judea
353:
327:Graph Theory
326:
319:
282:
263:
239:
204:
169:
152:
133:= 1, 2, 3, …
130:
119:
108:
84:
77:
73:
65:
61:
55:
53:
35:
32:graph theory
29:
615:Winkler, P.
270:grid graphs
36:orientation
311:References
117:vertices.
87:tournament
738:MathWorld
719:MathWorld
373:1304.2736
272:arise in
156:bijective
750:Category
657:(2006),
335:Springer
299:See also
95:polytree
692:2275714
641:1407581
584:0172275
555:1318743
510:2920058
462:2303897
412:0357214
223:colored
200:bridges
145:in the
142:A001174
690:
680:
639:
582:
553:
508:
498:
460:
410:
341:
38:of an
662:(PDF)
458:JSTOR
368:arXiv
331:(PDF)
135:) is
34:, an
678:ISBN
496:ISBN
339:ISBN
147:OEIS
99:tree
93:. A
70:and
670:doi
629:doi
576:254
541:doi
488:doi
448:hdl
440:doi
264:An
205:An
186:of
111:– 2
30:In
752::
735:,
731:,
716:,
712:,
688:MR
686:,
676:,
664:,
637:MR
635:,
625:16
623:,
580:MR
574:,
551:MR
549:,
537:56
535:,
527:;
506:MR
504:,
494:,
478:;
456:,
446:,
436:46
434:,
408:MR
337:,
283:A
280:.
261:.
240:A
237:.
202:.
190:.
170:A
149:).
101:.
85:A
76:,
64:,
46:.
672::
644:.
631::
603:.
587:.
558:.
543::
513:.
490::
465:.
450::
442::
415:.
377:.
370::
348:.
227:k
219:k
188:G
180:G
131:n
126:n
115:n
109:n
107:2
80:)
78:x
74:y
72:(
68:)
66:y
62:x
60:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.