|
道路 (图论)在图论中，一个图中一条道路或稱路徑（path）是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。  道路与圈是图论中的基本概念，在大部分图论教材中的绪论一节会介绍。例如参见 Bondy and Murty (1976)、Gibbons (1985) 或 Diestel (2005)、Korte et al. (1990) 包含了图中关于道路的更高等算法论题。 不同类型的道路相同的概念用于无向图与有向图，边的方向为从一个顶点到下一个顶点。通常术语有向道路与有向圈用于有向情形。 一个没有重复顶点的道路称为简单道路，而一个除了起点与终点没有重复顶点的道路叫做简单圈。在现代图论中，大多数蕴含了“简单”，比如“圈”意味着“简单圈”而“道路”意味着“简单道路”，但这种约定也不总是总被遵守，特别是在应用图论中。一些作者（比如 Bondy and Murty 1976）使用术语“漫游”（walk）表示一个顶点或边可以重复的道路，而将术语“道路”保留给简单道路。 一条使得没有图的边连接道路中两个不相邻顶点的道路称为导出道路。 一个包含图中所有顶点的简单圈称为哈密顿圈。 如果两条道路没有任何公共内部顶点则称为无关的（或内部顶点不交）。 一条道路的长度是这条道路使用的边数，重复道路算上重复次数。在单顶点情形长度可以为零。 一个加权图在图中的每条边上给出一个值（权重）。加权图中一条道路的权是经过的边的权之和。有时使用成本（cost）或长度一词代替权。 相关条目参考文献
|
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia
