755:
algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:
508:
384:
261:
872:
898:
918:
821:
801:
778:
406:
282:
1034:
By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
1057:
112:
consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs,
197:
71:
162:. The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is
833:
701:
536:—that is, a vertex whose distance from its furthest vertex is equal to the radius, equivalently, a vertex
17:
960:
47:
1069:
The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
728:
143:
689:
is one for which every pair of vertices has a unique shortest path connecting them. For example, all
569:—that is, a vertex whose distance from its furthest vertex is equal to the diameter. Formally,
990:
Bouttier, Jérémie; Di
Francesco, P.; Guitter, E. (July 2003). "Geodesic distance in planar graphs".
1113:
951:
163:
1118:
956:
941:
158:
defined over a set of points in terms of distances in a graph defined over the set is called a
1108:
964:
824:
740:
518:
514:
51:
43:
66:. Notice that there may be more than one shortest path between two vertices. If there is no
1009:
266:
It can be thought of as how far a node is from the node most distant from it in the graph.
8:
936:
877:
690:
67:
1013:
1025:
999:
903:
806:
786:
763:
677:
1021:
704:. In this case it is assumed that the weight of an edge represents its length or, for
1092:, Theory of graphs , Colloquium Publications, American Mathematical Society, p. 104
1046:
1029:
1017:
705:
1049:
680:
of the graph's vertices into subsets by their distances from the starting vertex.
931:
672:
503:{\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).}
379:{\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).}
685:
78:
1089:
1102:
752:
396:
of a graph is the maximum eccentricity of any vertex in the graph. That is,
969:
155:
35:
521:. The greatest length of any of these paths is the diameter of the graph.
400:
is the greatest distance between any pair of vertices or, alternatively,
1004:
31:
946:
146:, and it might be the case that one is defined while the other is not.
276:
of a graph is the minimum eccentricity of any vertex or, in symbols,
989:
746:
70:
connecting the two vertices, i.e., if they belong to different
712:
of the interaction, and the weighted shortest-path distance
74:, then conventionally the distance is defined as infinite.
104:
is defined as the length of a shortest directed path from
1080:
F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
906:
880:
836:
809:
789:
766:
409:
285:
200:
27:
Length of shortest path between two nodes of a graph
912:
892:
866:
815:
795:
772:
502:
378:
256:{\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}
255:
1100:
747:Algorithm for finding pseudo-peripheral vertices
513:To find the diameter of a graph, first find the
464:
448:
417:
340:
324:
293:
217:
58:) connecting them. This is also known as the
727:is the minimum sum of weights across all the
867:{\displaystyle \epsilon (v)>\epsilon (u)}
783:Among all the vertices that are as far from
676:of the graph, given a starting vertex, is a
1003:
621:is pseudo-peripheral if, for each vertex
14:
1101:
597:has the property that, for any vertex
1045:
700:generalises the geodesic distance to
149:
127:does not necessarily coincide with
24:
191:and any other vertex; in symbols,
25:
1130:
1054:MathWorld--A Wolfram Web Resource
743:for more details and algorithms.
617:as possible. Formally, a vertex
187:is the greatest distance between
1060:from the original on 2008-04-23
698:weighted shortest-path distance
1083:
1074:
1039:
983:
920:is a pseudo-peripheral vertex.
861:
855:
846:
840:
494:
482:
441:
435:
370:
358:
317:
311:
247:
235:
210:
204:
13:
1:
1022:10.1016/S0550-3213(03)00355-9
900:and repeat with step 2, else
565:is one whose eccentricity is
532:is one whose eccentricity is
50:is the number of edges in a
7:
924:
10:
1135:
976:
592:pseudo-peripheral vertex
957:Degree diameter problem
561:in a graph of diameter
942:Betweenness centrality
914:
894:
868:
817:
797:
774:
504:
380:
257:
64:shortest-path distance
915:
895:
869:
818:
798:
775:
741:shortest path problem
528:in a graph of radius
517:between each pair of
505:
381:
258:
96:between two vertices
1056:. Wolfram Research.
904:
878:
834:
823:be one with minimal
807:
787:
764:
613:is as far away from
605:is as far away from
407:
283:
198:
72:connected components
1014:2003NuPhB.663..535B
937:Resistance distance
893:{\displaystyle u=v}
1047:Weisstein, Eric W.
910:
890:
864:
813:
793:
770:
609:as possible, then
500:
478:
462:
431:
376:
354:
338:
307:
253:
231:
992:Nuclear Physics B
913:{\displaystyle u}
816:{\displaystyle v}
803:as possible, let
796:{\displaystyle u}
773:{\displaystyle u}
751:Often peripheral
573:is peripheral if
559:peripheral vertex
463:
447:
416:
339:
323:
292:
216:
142:—so it is just a
77:In the case of a
60:geodesic distance
16:(Redirected from
1126:
1093:
1087:
1081:
1078:
1072:
1071:
1066:
1065:
1050:"Graph Geodesic"
1043:
1037:
1036:
1007:
1005:cond-mat/0303272
987:
919:
917:
916:
911:
899:
897:
896:
891:
873:
871:
870:
865:
822:
820:
819:
814:
802:
800:
799:
794:
779:
777:
776:
771:
760:Choose a vertex
738:
734:
726:
706:complex networks
666:
648:, it holds that
647:
624:
620:
616:
612:
608:
604:
600:
596:
586:
572:
568:
564:
553:
539:
535:
531:
509:
507:
506:
501:
477:
461:
430:
399:
395:
385:
383:
382:
377:
353:
337:
306:
275:
262:
260:
259:
254:
230:
190:
186:
182:
150:Related concepts
141:
126:
111:
107:
103:
99:
95:
21:
1134:
1133:
1129:
1128:
1127:
1125:
1124:
1123:
1114:Metric geometry
1099:
1098:
1097:
1096:
1088:
1084:
1079:
1075:
1063:
1061:
1044:
1040:
988:
984:
979:
974:
932:Distance matrix
927:
905:
902:
901:
879:
876:
875:
835:
832:
831:
808:
805:
804:
788:
785:
784:
765:
762:
761:
749:
736:
732:
713:
702:weighted graphs
673:level structure
649:
626:
622:
618:
614:
610:
606:
602:
598:
594:
574:
570:
566:
562:
541:
537:
533:
529:
467:
451:
420:
408:
405:
404:
397:
393:
343:
327:
296:
284:
281:
280:
273:
220:
199:
196:
195:
188:
184:
173:
152:
128:
113:
109:
105:
101:
97:
82:
54:(also called a
28:
23:
22:
15:
12:
11:
5:
1132:
1122:
1121:
1119:Graph distance
1116:
1111:
1095:
1094:
1082:
1073:
1038:
998:(3): 535–567.
981:
980:
978:
975:
973:
972:
967:
954:
949:
944:
939:
934:
928:
926:
923:
922:
921:
909:
889:
886:
883:
863:
860:
857:
854:
851:
848:
845:
842:
839:
828:
812:
792:
781:
769:
748:
745:
693:are geodetic.
686:geodetic graph
526:central vertex
511:
510:
499:
496:
493:
490:
487:
484:
481:
476:
473:
470:
466:
460:
457:
454:
450:
446:
443:
440:
437:
434:
429:
426:
423:
419:
415:
412:
387:
386:
375:
372:
369:
366:
363:
360:
357:
352:
349:
346:
342:
336:
333:
330:
326:
322:
319:
316:
313:
310:
305:
302:
299:
295:
291:
288:
264:
263:
252:
249:
246:
243:
240:
237:
234:
229:
226:
223:
219:
215:
212:
209:
206:
203:
151:
148:
79:directed graph
56:graph geodesic
26:
18:Graph diameter
9:
6:
4:
3:
2:
1131:
1120:
1117:
1115:
1112:
1110:
1107:
1106:
1104:
1091:
1086:
1077:
1070:
1059:
1055:
1051:
1048:
1042:
1035:
1031:
1027:
1023:
1019:
1015:
1011:
1006:
1001:
997:
993:
986:
982:
971:
968:
966:
962:
958:
955:
953:
950:
948:
945:
943:
940:
938:
935:
933:
930:
929:
907:
887:
884:
881:
858:
852:
849:
843:
837:
829:
826:
810:
790:
782:
767:
759:
758:
757:
754:
753:sparse matrix
744:
742:
730:
724:
720:
716:
711:
707:
703:
699:
694:
692:
688:
687:
681:
679:
675:
674:
668:
664:
660:
656:
652:
645:
641:
637:
633:
629:
593:
588:
585:
581:
577:
560:
555:
552:
548:
544:
527:
522:
520:
516:
515:shortest path
497:
491:
488:
485:
479:
474:
471:
468:
458:
455:
452:
444:
438:
432:
427:
424:
421:
413:
410:
403:
402:
401:
392:
373:
367:
364:
361:
355:
350:
347:
344:
334:
331:
328:
320:
314:
308:
303:
300:
297:
289:
286:
279:
278:
277:
272:
267:
250:
244:
241:
238:
232:
227:
224:
221:
213:
207:
201:
194:
193:
192:
180:
176:
172:
167:
165:
161:
157:
147:
145:
139:
135:
131:
124:
120:
116:
93:
89:
85:
81:the distance
80:
75:
73:
69:
65:
61:
57:
53:
52:shortest path
49:
45:
41:
37:
33:
19:
1109:Graph theory
1085:
1076:
1068:
1062:. Retrieved
1053:
1041:
1033:
995:
991:
985:
970:Metric graph
750:
722:
718:
714:
709:
697:
695:
684:
682:
671:
669:
662:
658:
654:
650:
643:
639:
635:
631:
627:
591:
589:
583:
579:
575:
558:
556:
550:
546:
542:
525:
523:
512:
390:
388:
270:
268:
265:
183:of a vertex
178:
174:
171:eccentricity
170:
168:
160:graph metric
159:
156:metric space
153:
144:quasi-metric
137:
133:
129:
122:
118:
114:
91:
87:
83:
76:
63:
59:
55:
42:between two
39:
36:graph theory
32:mathematical
29:
1090:Øystein Ore
731:connecting
1103:Categories
1064:2008-04-23
947:Centrality
739:. See the
540:such that
1030:119594729
952:Closeness
874:then set
853:ϵ
838:ϵ
678:partition
472:∈
456:∈
433:ϵ
425:∈
348:∈
332:∈
309:ϵ
301:∈
225:∈
202:ϵ
164:connected
34:field of
1058:Archived
965:digraphs
925:See also
519:vertices
391:diameter
44:vertices
40:distance
1010:Bibcode
30:In the
1028:
961:graphs
825:degree
271:radius
38:, the
1026:S2CID
1000:arXiv
977:Notes
729:paths
691:trees
625:with
601:, if
48:graph
46:in a
963:and
959:for
850:>
735:and
710:cost
708:the
696:The
657:) =
638:) =
582:) =
549:) =
389:The
269:The
169:The
100:and
68:path
1018:doi
996:663
830:If
465:max
449:max
418:max
341:max
325:min
294:min
218:max
108:to
62:or
1105::
1067:.
1052:.
1032:.
1024:.
1016:.
1008:.
994:.
721:,
683:A
670:A
667:.
590:A
587:.
557:A
554:.
524:A
166:.
154:A
1020::
1012::
1002::
908:u
888:v
885:=
882:u
862:)
859:u
856:(
847:)
844:v
841:(
827:.
811:v
791:u
780:.
768:u
737:v
733:u
725:)
723:v
719:u
717:(
715:d
665:)
663:v
661:(
659:ϵ
655:u
653:(
651:ϵ
646:)
644:v
642:(
640:ϵ
636:v
634:,
632:u
630:(
628:d
623:u
619:v
615:u
611:v
607:v
603:u
599:u
595:v
584:d
580:v
578:(
576:ϵ
571:v
567:d
563:d
551:r
547:v
545:(
543:ϵ
538:v
534:r
530:r
498:.
495:)
492:u
489:,
486:v
483:(
480:d
475:V
469:u
459:V
453:v
445:=
442:)
439:v
436:(
428:V
422:v
414:=
411:d
398:d
394:d
374:.
371:)
368:u
365:,
362:v
359:(
356:d
351:V
345:u
335:V
329:v
321:=
318:)
315:v
312:(
304:V
298:v
290:=
287:r
274:r
251:.
248:)
245:u
242:,
239:v
236:(
233:d
228:V
222:u
214:=
211:)
208:v
205:(
189:v
185:v
181:)
179:v
177:(
175:ϵ
140:)
138:u
136:,
134:v
132:(
130:d
125:)
123:v
121:,
119:u
117:(
115:d
110:v
106:u
102:v
98:u
94:)
92:v
90:,
88:u
86:(
84:d
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.