349:
to the
Pfaffian regardless of which orientation is used; the choice of a Pfaffian orientation ensures that these contributions all have the same sign as each other, so that none of them cancel. This result stands in contrast to the much higher computational complexity of counting matchings in
362:
is
Pfaffian. An orientation in which each face of a planar graph has an odd number of clockwise-oriented edges is automatically Pfaffian. Such an orientation can be found by starting with an arbitrary orientation of a
28:
assigns a direction to each edge, so that certain cycles (the "even central cycles") have an odd number of edges in each direction. When a graph has a
Pfaffian orientation, the orientation can be used to count the
371:, and their orientations can be chosen according to a bottom-up traversal of the dual spanning tree in order to ensure that each face of the original graph has an odd number of clockwise edges.
548:
482:
441:
405:
112:
75:
512:
347:
308:
272:
252:
225:
205:
185:
162:
287:
for counting the number of perfect matchings in a given graph. In this algorithm, the orientations of the edges are used to assign the values
648:
799:
699:
Little, Charles H. C. (1974), "An extension of
Kasteleyn's method of enumerating the 1-factors of planar graphs",
725:
134:
in which every even central cycle is oddly oriented. The terms of this definition have the following meanings:
794:
514:
along shared edges. The same gluing structure can be used to obtain a
Pfaffian orientation for these graphs.
733:
729:
621:
579:
131:
41:, which always have Pfaffian orientations. More generally, every graph that does not have the
520:
454:
413:
377:
84:
47:
554:, it is possible to determine whether a Pfaffian orientation exists, and if so find one, in
775:
712:
701:
Combinatorial
Mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973)
683:
658:
605:
490:
329:
290:
142:
8:
625:
448:
407:-minor-free graph has a Pfaffian orientation. These are the graphs that do not have the
763:
745:
257:
237:
210:
190:
170:
147:
644:
755:
671:
636:
591:
228:
127:
30:
25:
771:
708:
679:
654:
601:
555:
551:
484:-minor-free graphs are formed by gluing together copies of planar graphs and the
367:
of the graph. The remaining edges, not in this tree, form a spanning tree of the
596:
485:
788:
408:
364:
284:
42:
34:
359:
326:) gives the number of perfect matchings. Each perfect matching contributes
311:
38:
17:
736:(1999), "Permanents, Pfaffian orientations, and even directed circuits",
444:
323:
319:
138:
An orientation is an assignment of a direction to each edge of the graph.
78:
640:
368:
358:
A graph is said to be
Pfaffian if it has a Pfaffian orientation. Every
767:
750:
114:
does not, nor do infinitely many other minimal non-Pfaffian graphs.
759:
315:
231:; central cycles are also sometimes called alternating circuits.
283:
Pfaffian orientations have been studied in connection with the
550:, there are infinitely many minimal non-Pfaffian graphs. For
274:
is consistent with an odd number of edges in the orientation.
635:, vol. 3, Zürich: Eur. Math. Soc., pp. 963–984,
724:
523:
493:
457:
416:
380:
332:
293:
260:
254:
is oddly oriented if each of the two orientations of
240:
213:
193:
173:
150:
87:
50:
278:
633:International Congress of Mathematicians. Vol. III
542:
506:
476:
435:
399:
341:
302:
266:
246:
219:
199:
179:
156:
106:
69:
786:
164:is even if it contains an even number of edges.
33:of the graph. This is the main idea behind the
626:"A survey of Pfaffian orientations of graphs"
674:(1967), "Graph theory and crystal physics",
577:
678:, London: Academic Press, pp. 43–110,
749:
670:
595:
582:(2008), "Minimally non-Pfaffian graphs",
207:formed by removing all the vertices of
787:
698:
620:
676:Graph Theory and Theoretical Physics
573:
571:
694:
692:
616:
614:
13:
718:
353:
37:for counting perfect matchings in
14:
811:
568:
279:Application to counting matchings
703:, Lecture Notes in Mathematics,
689:
664:
611:
81:has a Pfaffian orientation, but
584:Journal of Combinatorial Theory
187:is central if the subgraph of
117:
1:
561:
443:(which is not Pfaffian) as a
7:
707:, Springer, Berlin: 63–72,
10:
816:
597:10.1016/j.jctb.2007.12.005
314:of the graph. Then, the
310:to the variables in the
800:Matching (graph theory)
543:{\displaystyle K_{3,3}}
477:{\displaystyle K_{3,3}}
436:{\displaystyle K_{3,3}}
400:{\displaystyle K_{3,3}}
107:{\displaystyle K_{3,3}}
70:{\displaystyle K_{3,3}}
544:
508:
478:
437:
401:
374:More generally, every
343:
304:
268:
248:
221:
201:
181:
158:
108:
71:
738:Annals of Mathematics
545:
509:
507:{\displaystyle K_{5}}
479:
438:
402:
344:
342:{\displaystyle \pm 1}
305:
303:{\displaystyle \pm 1}
269:
249:
222:
202:
182:
159:
109:
72:
795:Graph theory objects
521:
491:
455:
414:
378:
330:
318:of this matrix (the
291:
258:
238:
211:
191:
171:
148:
124:Pfaffian orientation
85:
48:
22:Pfaffian orientation
540:
504:
474:
433:
397:
350:arbitrary graphs.
339:
300:
264:
244:
217:
197:
177:
154:
104:
67:
740:, Second Series,
650:978-3-98547-038-9
578:Norine, Serguei;
267:{\displaystyle C}
247:{\displaystyle C}
220:{\displaystyle C}
200:{\displaystyle G}
180:{\displaystyle C}
157:{\displaystyle C}
31:perfect matchings
807:
779:
778:
753:
722:
716:
715:
696:
687:
686:
672:Kasteleyn, P. W.
668:
662:
661:
641:10.4171/022-3/47
630:
618:
609:
608:
599:
590:(5): 1038–1055,
575:
552:bipartite graphs
549:
547:
546:
541:
539:
538:
513:
511:
510:
505:
503:
502:
483:
481:
480:
475:
473:
472:
449:Wagner's theorem
442:
440:
439:
434:
432:
431:
406:
404:
403:
398:
396:
395:
348:
346:
345:
340:
309:
307:
306:
301:
273:
271:
270:
265:
253:
251:
250:
245:
229:perfect matching
226:
224:
223:
218:
206:
204:
203:
198:
186:
184:
183:
178:
163:
161:
160:
155:
128:undirected graph
113:
111:
110:
105:
103:
102:
76:
74:
73:
68:
66:
65:
26:undirected graph
815:
814:
810:
809:
808:
806:
805:
804:
785:
784:
783:
782:
726:Robertson, Neil
723:
719:
697:
690:
669:
665:
651:
628:
619:
612:
576:
569:
564:
556:polynomial time
528:
524:
522:
519:
518:
498:
494:
492:
489:
488:
462:
458:
456:
453:
452:
421:
417:
415:
412:
411:
385:
381:
379:
376:
375:
356:
354:Pfaffian graphs
331:
328:
327:
292:
289:
288:
281:
259:
256:
255:
239:
236:
235:
212:
209:
208:
192:
189:
188:
172:
169:
168:
149:
146:
145:
120:
92:
88:
86:
83:
82:
55:
51:
49:
46:
45:
12:
11:
5:
813:
803:
802:
797:
781:
780:
760:10.2307/121059
744:(3): 929–975,
730:Seymour, P. D.
717:
688:
663:
649:
610:
566:
565:
563:
560:
537:
534:
531:
527:
501:
497:
486:complete graph
471:
468:
465:
461:
430:
427:
424:
420:
394:
391:
388:
384:
355:
352:
338:
335:
299:
296:
280:
277:
276:
275:
263:
243:
232:
216:
196:
176:
165:
153:
139:
119:
116:
101:
98:
95:
91:
64:
61:
58:
54:
9:
6:
4:
3:
2:
812:
801:
798:
796:
793:
792:
790:
777:
773:
769:
765:
761:
757:
752:
747:
743:
739:
735:
734:Thomas, Robin
731:
727:
721:
714:
710:
706:
702:
695:
693:
685:
681:
677:
673:
667:
660:
656:
652:
646:
642:
638:
634:
627:
623:
622:Thomas, Robin
617:
615:
607:
603:
598:
593:
589:
585:
581:
580:Thomas, Robin
574:
572:
567:
559:
557:
553:
535:
532:
529:
525:
515:
499:
495:
487:
469:
466:
463:
459:
450:
446:
428:
425:
422:
418:
410:
409:utility graph
392:
389:
386:
382:
372:
370:
366:
365:spanning tree
361:
351:
336:
333:
325:
321:
317:
313:
297:
294:
286:
285:FKT algorithm
261:
241:
233:
230:
214:
194:
174:
166:
151:
144:
140:
137:
136:
135:
133:
129:
125:
115:
99:
96:
93:
89:
80:
62:
59:
56:
52:
44:
43:utility graph
40:
39:planar graphs
36:
35:FKT algorithm
32:
27:
23:
19:
751:math/9911268
741:
737:
720:
704:
700:
675:
666:
632:
587:
586:, Series B,
583:
516:
373:
360:planar graph
357:
312:Tutte matrix
282:
123:
121:
21:
18:graph theory
15:
517:Along with
445:graph minor
324:determinant
320:square root
132:orientation
118:Definitions
79:graph minor
789:Categories
562:References
369:dual graph
334:±
295:±
624:(2006),
316:Pfaffian
167:A cycle
776:1740989
713:0382062
684:0253689
659:2275714
606:2442595
322:of its
774:
768:121059
766:
711:
682:
657:
647:
604:
451:, the
234:Cycle
227:has a
130:is an
126:of an
24:of an
764:JSTOR
746:arXiv
629:(PDF)
447:. By
143:cycle
77:as a
645:ISBN
20:, a
756:doi
742:150
705:403
637:doi
592:doi
16:In
791::
772:MR
770:,
762:,
754:,
732:;
728:;
709:MR
691:^
680:MR
655:MR
653:,
643:,
631:,
613:^
602:MR
600:,
588:98
570:^
558:.
141:A
122:A
758::
748::
639::
594::
536:3
533:,
530:3
526:K
500:5
496:K
470:3
467:,
464:3
460:K
429:3
426:,
423:3
419:K
393:3
390:,
387:3
383:K
337:1
298:1
262:C
242:C
215:C
195:G
175:C
152:C
100:3
97:,
94:3
90:K
63:3
60:,
57:3
53:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.