31:
221:, vertices that belong to every path between some pair of other vertices. The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints. Analogously to bridgeless graphs being 2-edge-connected, graphs without articulation vertices are
39:
200:
on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths connecting them. (Every vertex is related to itself via two length-zero paths, which are identical but nevertheless edge-disjoint.) The equivalence classes of this relation are called
97:
This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see
904:
1012:, stopping at the first vertex that is marked as visited. During such a traversal, every traversed vertex is marked as visited. Thus, a traversal stops at the latest at
851:
431:
713:
644:
552:
463:
183:
157:
944:
924:
816:
796:
773:
753:
733:
684:
664:
612:
592:
572:
523:
503:
483:
396:
369:
346:
321:
131:
279:(1978 and 1979, independently), which states that every bridgeless graph admits a multi-set of simple cycles which contains each edge exactly twice.
981:), giving a general framework for testing 2-edge- and 2-vertex-connectivity (which extends to linear-time 3-edge- and 3-vertex-connectivity tests).
1380:
245:
75:
1318:
1244:
268:
272:
71:
1483:
646:, the highest preorder label reachable by a path for which all but the last edge stays within the subtree rooted at
222:
102:
98:
67:
253:
205:, and the bridges of the graph are exactly the edges whose endpoints belong to different components. The
1197:
974:
190:
1437:
856:
197:
79:
1045:
958:
326:
257:
218:
186:
1222:
1449:
1345:
1202:
997:
261:
83:
961:. Chain decompositions do not only allow to compute all bridges of a graph, they also allow to
1376:
1240:
1184:
1126:
291:
algorithm (linear in the number of edges) for finding the bridges in a graph was described by
249:
1459:
1408:
1368:
1335:
1327:
1284:
1232:
1226:
821:
1420:
1296:
1254:
404:
1416:
1313:
1292:
1250:
1016:
and forms either a directed path or cycle, beginning with v; we call this path or cycle a
992:
and can be computed very simply: Let every vertex be marked as unvisited. For each vertex
689:
620:
528:
439:
300:
276:
375:
and number the nodes. Parent nodes in the forest now have lower numbers than child nodes.
162:
136:
1268:
929:
909:
801:
781:
758:
738:
718:
669:
649:
597:
577:
557:
508:
488:
468:
381:
372:
354:
331:
306:
209:
of the graph has a vertex for every nontrivial component and an edge for every bridge.
116:
1372:
1231:, Graduate Texts in Mathematics, vol. 184, New York: Springer-Verlag, p. 6,
1477:
1412:
1396:
1272:
292:
1316:(1939), "A theorem on graphs, with an application to a problem of traffic control",
1004:, traverse every backedge (i.e. every edge not in the DFS tree) that is incident to
159:
bridges, since adding additional edges must create a cycle. The graphs with exactly
47:
288:
229:
17:
244:
is a graph that does not have any bridges. Equivalent conditions are that each
1463:
1340:
1236:
966:
78:. Equivalently, an edge is a bridge if and only if it is not contained in any
30:
485:
by a path for which all but the last edge stays within the subtree rooted at
984:
Chain decompositions are special ear decompositions depending on a DFS-tree
1275:(1992), "Maintaining bridge-connected and biconnected components on-line",
1349:
1288:
38:
433:
for this node, by adding one to the sum of its children's descendants.
666:. This is the maximum of the set consisting of the preorder label of
505:. This is the minimum of the set consisting of the preorder label of
1363:
Jaeger, F. (1985), "A survey of the cycle double cover conjecture",
1331:
1454:
1367:, North-Holland Mathematics Studies, vol. 27, pp. 1–12,
37:
29:
189:, and the graphs in which every edge is a bridge are exactly the
398:
in preorder (denoting each node using its preorder number), do:
27:
Edge in node-link graph whose removal would disconnect the graph
1440:(2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity",
34:
A graph with 16 vertices and six bridges (highlighted in red)
82:. For a connected graph, a bridge can uniquely determine a
232:, every cut vertex is an endpoint of at least one bridge.
1008:
and follow the path of tree-edges back to the root of
1076:
be a chain decomposition of a simple connected graph
932:
912:
859:
824:
804:
784:
761:
741:
721:
692:
672:
652:
623:
600:
580:
560:
531:
511:
491:
471:
442:
407:
384:
357:
334:
309:
165:
139:
119:
1399:(1974), "A note on finding the bridges of a graph",
1365:
Annals of
Discrete Mathematics 27 – Cycles in Graphs
1024:th chain found by this procedure is referred to as
735:and of the preorder labels of nodes reachable from
574:and of the preorder labels of nodes reachable from
267:An important open problem involving bridges is the
938:
918:
898:
845:
810:
790:
767:
747:
727:
707:
678:
658:
638:
606:
586:
566:
546:
517:
497:
477:
457:
425:
390:
363:
340:
315:
177:
151:
125:
42:An undirected connected graph with no bridge edges
1087:is 2-edge-connected if and only if the chains in
74:whose deletion increases the graph's number of
1056:The following characterizations then allow to
217:Bridges are closely related to the concept of
8:
957:A very simple bridge-finding algorithm uses
1308:
1306:
465:, the lowest preorder label reachable from
295:in 1974. It performs the following steps:
1453:
1432:
1430:
1339:
931:
911:
858:
823:
803:
783:
760:
740:
720:
691:
671:
651:
622:
599:
579:
559:
530:
510:
490:
470:
441:
406:
401:Compute the number of forest descendants
383:
356:
333:
308:
164:
138:
118:
953:Bridge-finding with chain decompositions
282:
1214:
260:) that every connected component has a
196:In every undirected graph, there is an
1068:efficiently, including all bridges of
1135:is 2-vertex-connected if and only if
7:
252:, that each connected component is
1165:is the first vertex of a cycle in
25:
1319:The American Mathematical Monthly
1110:is not contained in any chain in
283:Tarjan's bridge-finding algorithm
1161:is a cut vertex if and only if
899:{\displaystyle H(w)<w+ND(w)}
755:by edges that do not belong to
594:by edges that do not belong to
213:Relation to vertex connectivity
1442:Information Processing Letters
1401:Information Processing Letters
893:
887:
869:
863:
834:
828:
702:
696:
633:
627:
541:
535:
452:
446:
420:
414:
1:
1373:10.1016/S0304-0208(08)72993-1
269:cycle double cover conjecture
1413:10.1016/0020-0190(74)90003-9
1157:in a 2-edge-connected graph
1106:is a bridge if and only if
203:2-edge-connected components
94:if it contains no bridges.
1500:
133:nodes can contain at most
1464:10.1016/j.ipl.2013.01.016
1237:10.1007/978-1-4612-0619-4
1139:has minimum degree 2 and
348:from the spanning forest
185:bridges are exactly the
103:Glossary of graph theory
86:. A graph is said to be
1179:is 2-vertex-connected,
1185:open ear decomposition
1060:several properties of
940:
920:
900:
847:
846:{\displaystyle L(w)=w}
812:
792:
769:
749:
729:
709:
680:
660:
640:
608:
588:
568:
548:
519:
499:
479:
459:
427:
392:
365:
342:
317:
250:open ear decomposition
179:
153:
127:
43:
35:
1198:Biconnected component
1146:is the only cycle in
1121:is 2-edge-connected,
941:
921:
901:
848:
813:
793:
770:
750:
730:
710:
681:
661:
641:
609:
589:
569:
549:
520:
500:
480:
460:
428:
426:{\displaystyle ND(v)}
393:
366:
343:
318:
219:articulation vertices
180:
154:
128:
41:
33:
959:chain decompositions
930:
910:
857:
822:
802:
782:
759:
739:
719:
708:{\displaystyle H(w)}
690:
670:
650:
639:{\displaystyle H(v)}
621:
598:
578:
558:
547:{\displaystyle L(w)}
529:
509:
489:
469:
458:{\displaystyle L(v)}
440:
405:
382:
355:
351:Traverse the forest
332:
307:
248:of the graph has an
198:equivalence relation
163:
137:
117:
76:connected components
1228:Modern Graph Theory
1046:chain decomposition
906:then the edge from
686:, of the values of
617:Similarly, compute
525:, of the values of
246:connected component
178:{\displaystyle n-1}
152:{\displaystyle n-1}
1484:Graph connectivity
1341:10338.dmlcz/101517
1289:10.1007/BF01758773
1269:Westbrook, Jeffery
1203:Cut (graph theory)
936:
916:
896:
843:
808:
788:
765:
745:
725:
715:at child nodes of
705:
676:
656:
636:
604:
584:
564:
554:at child nodes of
544:
515:
495:
475:
455:
423:
388:
361:
338:
313:
262:strong orientation
223:2-vertex-connected
175:
149:
123:
44:
36:
1382:978-0-444-87803-8
1273:Tarjan, Robert E.
1127:ear decomposition
939:{\displaystyle w}
919:{\displaystyle v}
811:{\displaystyle v}
798:with parent node
791:{\displaystyle w}
768:{\displaystyle F}
748:{\displaystyle v}
728:{\displaystyle v}
679:{\displaystyle v}
659:{\displaystyle v}
607:{\displaystyle F}
587:{\displaystyle v}
567:{\displaystyle v}
518:{\displaystyle v}
498:{\displaystyle v}
478:{\displaystyle v}
391:{\displaystyle v}
364:{\displaystyle F}
341:{\displaystyle F}
316:{\displaystyle G}
236:Bridgeless graphs
207:bridge-block tree
126:{\displaystyle n}
109:Trees and forests
16:(Redirected from
1491:
1468:
1466:
1457:
1438:Schmidt, Jens M.
1434:
1425:
1423:
1397:Tarjan, R. Endre
1393:
1387:
1385:
1360:
1354:
1352:
1343:
1310:
1301:
1299:
1283:(5–6): 433–464,
1265:
1259:
1257:
1219:
945:
943:
942:
937:
925:
923:
922:
917:
905:
903:
902:
897:
852:
850:
849:
844:
817:
815:
814:
809:
797:
795:
794:
789:
774:
772:
771:
766:
754:
752:
751:
746:
734:
732:
731:
726:
714:
712:
711:
706:
685:
683:
682:
677:
665:
663:
662:
657:
645:
643:
642:
637:
613:
611:
610:
605:
593:
591:
590:
585:
573:
571:
570:
565:
553:
551:
550:
545:
524:
522:
521:
516:
504:
502:
501:
496:
484:
482:
481:
476:
464:
462:
461:
456:
432:
430:
429:
424:
397:
395:
394:
389:
370:
368:
367:
362:
347:
345:
344:
339:
322:
320:
319:
314:
258:Robbins' theorem
254:2-edge-connected
242:bridgeless graph
184:
182:
181:
176:
158:
156:
155:
150:
132:
130:
129:
124:
21:
18:Bridgeless graph
1499:
1498:
1494:
1493:
1492:
1490:
1489:
1488:
1474:
1473:
1472:
1471:
1436:
1435:
1428:
1395:
1394:
1390:
1383:
1362:
1361:
1357:
1332:10.2307/2303897
1312:
1311:
1304:
1267:
1266:
1262:
1247:
1221:
1220:
1216:
1211:
1194:
1170:
1144:
1040:
1036:
1029:
955:
928:
927:
908:
907:
855:
854:
820:
819:
800:
799:
780:
779:
757:
756:
737:
736:
717:
716:
688:
687:
668:
667:
648:
647:
619:
618:
596:
595:
576:
575:
556:
555:
527:
526:
507:
506:
487:
486:
467:
466:
438:
437:
403:
402:
380:
379:
353:
352:
330:
329:
305:
304:
301:spanning forest
285:
238:
215:
161:
160:
135:
134:
115:
114:
111:
28:
23:
22:
15:
12:
11:
5:
1497:
1495:
1487:
1486:
1476:
1475:
1470:
1469:
1448:(7): 241–244,
1426:
1407:(6): 160–161,
1388:
1381:
1355:
1326:(5): 281–283,
1314:Robbins, H. E.
1302:
1260:
1245:
1223:Bollobás, Béla
1213:
1212:
1210:
1207:
1206:
1205:
1200:
1193:
1190:
1189:
1188:
1173:
1168:
1151:
1142:
1130:
1115:
1096:
1038:
1034:
1027:
975:block-cut tree
954:
951:
950:
949:
948:
947:
935:
915:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
842:
839:
836:
833:
830:
827:
807:
787:
778:For each node
776:
764:
744:
724:
704:
701:
698:
695:
675:
655:
635:
632:
629:
626:
615:
603:
583:
563:
543:
540:
537:
534:
514:
494:
474:
454:
451:
448:
445:
434:
422:
419:
416:
413:
410:
387:
378:For each node
376:
360:
349:
337:
323:
312:
284:
281:
237:
234:
214:
211:
174:
171:
168:
148:
145:
142:
122:
110:
107:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1496:
1485:
1482:
1481:
1479:
1465:
1461:
1456:
1451:
1447:
1443:
1439:
1433:
1431:
1427:
1422:
1418:
1414:
1410:
1406:
1402:
1398:
1392:
1389:
1384:
1378:
1374:
1370:
1366:
1359:
1356:
1351:
1347:
1342:
1337:
1333:
1329:
1325:
1321:
1320:
1315:
1309:
1307:
1303:
1298:
1294:
1290:
1286:
1282:
1278:
1274:
1270:
1264:
1261:
1256:
1252:
1248:
1246:0-387-98488-7
1242:
1238:
1234:
1230:
1229:
1224:
1218:
1215:
1208:
1204:
1201:
1199:
1196:
1195:
1191:
1186:
1182:
1178:
1174:
1171:
1164:
1160:
1156:
1152:
1149:
1145:
1138:
1134:
1131:
1128:
1124:
1120:
1116:
1113:
1109:
1105:
1101:
1097:
1094:
1090:
1086:
1083:
1082:
1081:
1079:
1075:
1071:
1067:
1063:
1059:
1054:
1052:
1048:
1047:
1042:
1030:
1023:
1019:
1015:
1011:
1007:
1003:
1000:-numbers 1...
999:
996:in ascending
995:
991:
987:
982:
980:
976:
972:
968:
964:
960:
952:
933:
913:
890:
884:
881:
878:
875:
872:
866:
860:
840:
837:
831:
825:
805:
785:
777:
762:
742:
722:
699:
693:
673:
653:
630:
624:
616:
601:
581:
561:
538:
532:
512:
492:
472:
449:
443:
435:
417:
411:
408:
400:
399:
385:
377:
374:
358:
350:
335:
328:
327:Rooted forest
324:
310:
302:
298:
297:
296:
294:
293:Robert Tarjan
290:
280:
278:
274:
270:
265:
263:
259:
255:
251:
247:
243:
235:
233:
231:
226:
224:
220:
212:
210:
208:
204:
199:
194:
192:
188:
172:
169:
166:
146:
143:
140:
120:
113:A graph with
108:
106:
104:
100:
95:
93:
89:
85:
81:
77:
73:
69:
65:
61:
57:
53:
49:
40:
32:
19:
1445:
1441:
1404:
1400:
1391:
1364:
1358:
1323:
1317:
1280:
1277:Algorithmica
1276:
1263:
1227:
1217:
1180:
1176:
1166:
1162:
1158:
1154:
1147:
1140:
1136:
1132:
1122:
1118:
1111:
1107:
1103:
1099:
1092:
1088:
1084:
1077:
1073:
1069:
1065:
1061:
1057:
1055:
1050:
1044:
1032:
1025:
1021:
1017:
1013:
1009:
1005:
1001:
993:
989:
985:
983:
978:
970:
962:
956:
946:is a bridge.
286:
266:
241:
239:
227:
216:
206:
202:
195:
112:
96:
92:isthmus-free
91:
87:
63:
59:
55:
51:
48:graph theory
45:
289:linear time
230:cubic graph
1091:partition
1043:is then a
967:cut vertex
287:The first
88:bridgeless
1455:1209.0700
1153:A vertex
973:(and the
325:Create a
271:, due to
256:, or (by
170:−
144:−
1478:Category
1225:(1998),
1192:See also
1098:An edge
1058:read off
963:read off
436:Compute
373:preorder
277:Szekeres
60:cut-edge
1421:0349483
1350:2303897
1297:1154584
1255:1633290
1078:G=(V,E)
299:Find a
273:Seymour
191:forests
101:in the
64:cut arc
56:isthmus
1419:
1379:
1348:
1295:
1253:
1243:
1183:is an
1125:is an
1072:. Let
1020:. The
965:every
99:bridge
66:is an
52:bridge
1450:arXiv
1346:JSTOR
1209:Notes
1167:C - C
1064:from
1018:chain
818:, if
228:In a
187:trees
80:cycle
72:graph
70:of a
62:, or
1377:ISBN
1241:ISBN
1041:,...
873:<
853:and
275:and
68:edge
50:, a
1460:doi
1446:113
1409:doi
1369:doi
1336:hdl
1328:doi
1285:doi
1233:doi
1175:If
1117:If
1102:in
1049:of
1033:C=C
998:DFS
988:of
977:of
969:of
926:to
371:in
303:of
90:or
84:cut
46:In
1480::
1458:,
1444:,
1429:^
1417:MR
1415:,
1403:,
1375:,
1344:,
1334:,
1324:46
1322:,
1305:^
1293:MR
1291:,
1279:,
1271:;
1251:MR
1249:,
1239:,
1080:.
1053:.
1037:,C
1031:.
264:.
240:A
225:.
193:.
105:.
58:,
54:,
1467:.
1462::
1452::
1424:.
1411::
1405:2
1386:.
1371::
1353:.
1338::
1330::
1300:.
1287::
1281:7
1258:.
1235::
1187:.
1181:C
1177:G
1172:.
1169:1
1163:v
1159:G
1155:v
1150:.
1148:C
1143:1
1141:C
1137:G
1133:G
1129:.
1123:C
1119:G
1114:.
1112:C
1108:e
1104:G
1100:e
1095:.
1093:E
1089:C
1085:G
1074:C
1070:G
1066:C
1062:G
1051:G
1039:2
1035:1
1028:i
1026:C
1022:i
1014:v
1010:T
1006:v
1002:n
994:v
990:G
986:T
979:G
971:G
934:w
914:v
894:)
891:w
888:(
885:D
882:N
879:+
876:w
870:)
867:w
864:(
861:H
841:w
838:=
835:)
832:w
829:(
826:L
806:v
786:w
775:.
763:F
743:v
723:v
703:)
700:w
697:(
694:H
674:v
654:v
634:)
631:v
628:(
625:H
614:.
602:F
582:v
562:v
542:)
539:w
536:(
533:L
513:v
493:v
473:v
453:)
450:v
447:(
444:L
421:)
418:v
415:(
412:D
409:N
386:v
359:F
336:F
311:G
173:1
167:n
147:1
141:n
121:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
