624:. There are four kinds. One is a balanced circle. Two other kinds are a pair of unbalanced circles together with a connecting simple path, such that the two circles are either disjoint (then the connecting path has one end in common with each circle and is otherwise disjoint from both) or share just a single common vertex (in this case the connecting path is that single vertex). The fourth kind of circuit is a theta graph in which every circle is unbalanced.
612:
in the abstract sense, meaning that it is a submatroid of a matroid in which, for at least one basis, the set of lines generated by pairs of basis elements covers the whole matroid. Conversely, every abstract frame matroid is the frame matroid of some biased graph.
283:) is the result of any sequence of taking subgraphs and contracting edge sets. For biased graphs, as for graphs, it suffices to take a subgraph (which may be the whole graph) and then contract an edge set (which may be the empty set).
604:. An edge set is independent if each component contains either no circles or just one circle, which is unbalanced. (In matroid theory a half-edge acts like an unbalanced loop and a loose edge acts like a balanced loop.)
568:) becomes a half-edge. An edge with two endpoints that belong to different balanced components becomes a link, and an edge with two endpoints that belong to the same balanced component becomes a loop.
766:
A circuit is a balanced circle, a pair of unbalanced circles that are either disjoint or have just a common vertex, or a theta graph whose circles are all unbalanced.
380:
142:(no endpoints). The edges with two endpoints are of two kinds: a link has two distinct endpoints, while a loop has two coinciding endpoints.
39:, then the third circle of the theta graph is also in the list. A biased graph is a generalization of the combinatorial essentials of a
164:, and there are no half-edges, Ω is balanced. A balanced biased graph is (for most purposes) essentially the same as an ordinary graph.
963:
956:
390:
is a balanced loop or a loose edge, it is simply deleted. If it is an unbalanced loop or a half-edge, it and its vertex
139:
135:
88:
955:
Thomas
Zaslavsky (1999). A mathematical bibliography of signed and gain graphs and allied areas. 1999 edition:
974:
796:
Minors of the lift and extended lift matroids agree in part with minors of the biased graph. Deletions agree:
78:
36:
760:. The extra point acts exactly like an unbalanced loop or a half-edge, so we describe only the lift matroid.
74:
of circles; this by definition is a class of circles that satisfies the theta-graph property mentioned above.
996:
991:
925:. It is possible to prove theorems about multiary quasigroups by means of biased graphs (Zaslavsky, t.a.)
580:
associated with a biased graph, both of which generalize the cycle matroid of a graph (Zaslavsky, 1991).
560:) becomes a loose edge in the contraction. An edge with only one endpoint in a balanced component of (
763:
An edge set is independent if it contains either no circles or just one circle, which is unbalanced.
270:
212:
178:
972:
Thomas
Zaslavsky (2012), Associativity in multiary quasigroups: the way of biased expansions.
359:
910:
694:
437:).) The vertex set is the class of vertex sets of balanced components of the subgraph (
402:
as one endpoint becomes a half-edge at its other endpoint, while a loop or half-edge at
216:
985:
195:
145:
Linear classes of circles are a special case of linear subclasses of circuits in a
44:
32:
28:
245:(circle of length 2) is balanced lead to spikes and swirls (see Matroids, below).
123:
20:
934:
T. A. Dowling (1973), A class of geometric lattices based on finite groups.
922:
298:, with balanced circle class consisting of those balanced circles that are in
257:
249:
40:
658:
Minors of the frame matroid agree with minors of the biased graph; that is,
252:
or are generalizations of special kinds of gain graph. The latter include
941:
Thomas
Zaslavsky (1989), Biased graphs. I. Bias, balance, and gains.
697:
associated with a group (Dowling, 1973). The frame matroid of a biased 2
873:
609:
577:
552:) disappears. An edge with all endpoints in unbalanced components of (
146:
119:
948:
Thomas
Zaslavsky (1991), Biased graphs. II. The three matroids.
314:, is the subgraph with all vertices and all edges except those of
242:
913:), its combinatorial analog expanding a simple cycle of length
888:(see Examples, above) which has no balanced digons is called a
706:(see Examples, above) which has no balanced digons is called a
892:. Spikes are quite important in matroid structure theory.
600:(Ω), (Zaslavsky, 1989) has for its ground set the edge set
35:), such that if two circles in the list are contained in a
324:
of Ω is relatively complicated. To contract one edge
227:Ω may have underlying graph that is a cycle of length
194:
and is the biased graph obtained from an all-negative
118:
Biased graphs are interesting mostly because of their
655:, counting isolated vertices as balanced components.
362:
122:, but also because of their connection with multiary
190:
consists of the circles of even length, Ω is called
812:. Contractions agree only for balanced edge sets:
398:as an endpoint loses that endpoint, so a link with
224:
is the class of positive circles of a signed graph.
31:with a list of distinguished circles (edge sets of
960:, Dynamic Surveys in Combinatorics, #DS8, archived
374:
710:. It is important in matroid structure theory.
756:(Ω) is the extended lift matroid restricted to
177:. Contrabalanced biased graphs are related to
900:Just as a group expansion of a complete graph
832:is balanced, but not if it is unbalanced. If
248:Some kinds of biased graph are obtained from
8:
789:, counting isolated vertices, and ε is 0 if
328:, the procedure depends on the kind of edge
453:) has balanced components with vertex sets
950:Journal of Combinatorial Theory, Series B
943:Journal of Combinatorial Theory, Series B
936:Journal of Combinatorial Theory, Series B
361:
231:≥ 3 with all edges doubled. Call this a
16:Graph with a list of distinguished cycles
967:, Dynamic Surveys in Combinatorics, #DS8
651:is the number of balanced components of
544:that is not in a balanced component of (
616:The circuits of the matroid are called
95:. For instance, a circle belonging to
81:or edge set whose circles are all in
7:
965:Electronic Journal of Combinatorics
958:Electronic Journal of Combinatorics
728:(Ω) has for its ground set the set
394:are deleted; each other edge with
241:. Such biased graphs in which no
14:
211:, that is, closed under repeated
952:, Vol. 51, pp. 46–72.
945:, Vol. 47, pp. 32–52.
938:, Vol. 14, pp. 61–86.
872:of a graph denotes the ordinary
793:is balanced and 1 if it is not.
105:and one that does not belong to
785:is the number of components of
215:(when the result is a circle),
693:Frame matroids generalize the
1:
643:is the number of vertices of
540: ; thus, an endpoint of
290:of Ω consists of a subgraph
158:If every circle belongs to
1013:
518:in Ω that belongs to some
336:is a link, contract it in
978:, Vol. 83, pp. 1–66.
413:by an arbitrary edge set
975:Aequationes Mathematicae
769:The rank of an edge set
735:, which is the union of
627:The rank of an edge set
382:is a balanced circle of
294:of the underlying graph
134:A biased graph may have
909:encodes the group (see
879:The lift matroid of a 2
576:There are two kinds of
501:, becomes an edge of Ω/
375:{\displaystyle C\cup e}
273:of a biased graph Ω = (
254:biased expansion graphs
87:(and which contains no
43:and in particular of a
445:) of Ω. That is, if (
406:becomes a loose edge.
376:
352:is balanced if either
258:group expansion graphs
173:is empty, Ω is called
962:. Current edition:
720:extended lift matroid
596:) of a biased graph,
525:becomes the endpoint
409:In the contraction Ω/
377:
896:Multiary quasigroups
360:
310:, written Ω −
213:symmetric difference
344:in the contraction
256:, which generalize
179:bicircular matroids
138:(one endpoint) and
695:Dowling geometries
592:(sometimes called
505:and each endpoint
417:, the edge set is
372:
584:The frame matroid
201:The linear class
1004:
921:-ary (multiary)
911:Dowling geometry
714:The lift matroid
381:
379:
378:
373:
1012:
1011:
1007:
1006:
1005:
1003:
1002:
1001:
982:
981:
931:
917:+ 1 encodes an
908:
898:
887:
874:graphic matroid
836:is unbalanced,
748:
734:
727:
716:
705:
586:
574:
530:
523:
513:
492:
483:
468:
459:
358:
357:
306:of an edge set
267:
238:
155:
132:
130:Technical notes
17:
12:
11:
5:
1010:
1008:
1000:
999:
997:Matroid theory
994:
992:Graph families
984:
983:
980:
979:
970:
953:
946:
939:
930:
927:
904:
897:
894:
883:
746:
732:
725:
715:
712:
701:
618:frame circuits
585:
582:
573:
570:
528:
521:
509:
488:
481:
464:
457:
371:
368:
365:
266:
263:
262:
261:
246:
236:
225:
217:if and only if
199:
182:
175:contrabalanced
165:
154:
151:
131:
128:
126:. See below.
15:
13:
10:
9:
6:
4:
3:
2:
1009:
998:
995:
993:
990:
989:
987:
977:
976:
971:
968:
966:
961:
959:
954:
951:
947:
944:
940:
937:
933:
932:
928:
926:
924:
920:
916:
912:
907:
903:
895:
893:
891:
886:
882:
877:
875:
871:
867:
863:
859:
855:
851:
847:
843:
839:
835:
831:
827:
823:
819:
815:
811:
807:
803:
799:
794:
792:
788:
784:
780:
776:
772:
767:
764:
761:
759:
755:
752:
745:
742:
738:
731:
724:
721:
713:
711:
709:
704:
700:
696:
691:
689:
685:
681:
677:
673:
669:
665:
661:
656:
654:
650:
646:
642:
638:
634:
630:
625:
623:
622:bias circuits
619:
614:
611:
610:frame matroid
607:
603:
599:
595:
591:
590:frame matroid
583:
581:
579:
571:
569:
567:
563:
559:
555:
551:
547:
543:
539:
535:
531:
524:
517:
512:
508:
504:
500:
497:of Ω, not in
496:
491:
487:
480:
476:
472:
467:
463:
456:
452:
448:
444:
440:
436:
432:
428:
424:
420:
416:
412:
407:
405:
401:
397:
393:
389:
385:
369:
366:
363:
355:
351:
347:
343:
339:
335:
331:
327:
323:
319:
317:
313:
309:
305:
301:
297:
293:
289:
284:
282:
281:
276:
272:
264:
259:
255:
251:
247:
244:
240:
239:
230:
226:
223:
222:
218:
214:
210:
206:
205:
200:
197:
193:
189:
188:
183:
180:
176:
172:
171:
166:
163:
162:
157:
156:
152:
150:
148:
143:
141:
137:
129:
127:
125:
121:
116:
114:
110:
109:
104:
100:
99:
94:
90:
86:
85:
80:
75:
73:
69:
68:
63:
62:
57:
54:Ω is a pair (
53:
48:
46:
42:
38:
34:
33:simple cycles
30:
26:
22:
973:
964:
957:
949:
942:
935:
918:
914:
905:
901:
899:
889:
884:
880:
878:
869:
865:
861:
857:
853:
849:
845:
841:
837:
833:
829:
825:
821:
817:
813:
809:
805:
801:
797:
795:
790:
786:
782:
778:
774:
770:
768:
765:
762:
757:
753:
751:lift matroid
750:
743:
740:
736:
729:
722:
719:
717:
707:
702:
698:
692:
687:
683:
679:
675:
671:
667:
663:
659:
657:
652:
648:
644:
640:
636:
632:
628:
626:
621:
617:
615:
605:
601:
597:
594:bias matroid
593:
589:
587:
575:
565:
561:
557:
553:
549:
545:
541:
537:
533:
526:
519:
515:
510:
506:
502:
498:
494:
489:
485:
478:
474:
470:
465:
461:
454:
450:
446:
442:
438:
434:
430:
426:
422:
418:
414:
410:
408:
403:
399:
395:
391:
387:
383:
353:
349:
345:
341:
340:. A circle
337:
333:
329:
325:
321:
320:
315:
311:
307:
303:
299:
295:
291:
287:
285:
279:
278:
274:
268:
253:
234:
232:
228:
220:
219:
208:
203:
202:
196:signed graph
192:antibalanced
191:
186:
185:
174:
169:
168:
160:
159:
144:
133:
117:
112:
107:
106:
102:
97:
96:
92:
91:) is called
83:
82:
76:
72:linear class
71:
66:
65:
60:
59:
55:
52:biased graph
51:
50:Formally, a
49:
45:signed graph
25:biased graph
24:
18:
781:+ ε, where
741:extra point
493:. An edge
425:. (We let
322:Contraction
250:gain graphs
140:loose edges
124:quasigroups
37:theta graph
21:mathematics
986:Categories
929:References
923:quasigroup
808:(Ω)−
670:(Ω)−
136:half-edges
113:unbalanced
89:half-edges
41:gain graph
800:(Ω−
662:(Ω−
608:(Ω) is a
477:vertices
469:, then Ω/
367:∪
868:) where
777:−
739:with an
639:, where
635:−
572:Matroids
421:−
332:is. If
304:deletion
288:subgraph
233:biased 2
209:additive
153:Examples
120:matroids
103:balanced
93:balanced
79:subgraph
64:) where
749:. The
578:matroid
484:, ...,
460:, ...,
386:. If
302:. The
147:matroid
265:Minors
890:spike
708:swirl
536:in Ω/
271:minor
243:digon
70:is a
29:graph
27:is a
844:) =
824:(Ω)/
820:) =
804:) =
718:The
686:(Ω)/
682:) =
674:and
666:) =
647:and
588:The
473:has
23:, a
840:(Ω/
828:if
816:(Ω/
773:is
678:(Ω/
631:is
620:or
532:of
514:of
429:= (
356:or
207:is
184:If
167:If
111:is
101:is
19:In
988::
876:.
856:=
852:)/
690:.
564:,
556:,
548:,
449:,
441:,
433:,
318:.
286:A
277:,
269:A
149:.
115:.
77:A
58:,
47:.
969:.
919:n
915:n
906:n
902:K
885:n
881:C
870:M
866:S
864:/
862:G
860:(
858:M
854:S
850:G
848:(
846:M
842:S
838:M
834:S
830:S
826:S
822:M
818:S
814:M
810:S
806:L
802:S
798:L
791:S
787:S
783:c
779:c
775:n
771:S
758:E
754:L
747:0
744:e
737:E
733:0
730:E
726:0
723:L
703:n
699:C
688:S
684:M
680:S
676:M
672:S
668:M
664:S
660:M
653:S
649:b
645:G
641:n
637:b
633:n
629:S
606:M
602:E
598:M
566:S
562:V
558:S
554:V
550:S
546:V
542:e
538:S
534:e
529:i
527:V
522:i
520:V
516:e
511:i
507:v
503:S
499:S
495:e
490:k
486:V
482:1
479:V
475:k
471:S
466:k
462:V
458:1
455:V
451:S
447:V
443:S
439:V
435:E
431:V
427:G
423:S
419:E
415:S
411:S
404:v
400:v
396:v
392:v
388:e
384:G
370:e
364:C
354:C
350:e
348:/
346:G
342:C
338:G
334:e
330:e
326:e
316:S
312:S
308:S
300:H
296:G
292:H
280:B
275:G
260:.
237:n
235:C
229:n
221:B
204:B
198:.
187:B
181:.
170:B
161:B
108:B
98:B
84:B
67:B
61:B
56:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.