线图的概念最早是由Whitney在1932年提出的。在所有图的变换中,线图变换可能是研究最广泛的一种变换了。Whitney证明了除K3和K1,3外,两个连通图的边同构暗示了其点同构。关于线图有很多推广,例如：全图,中间图,团图,三角图,路图和超线图,等等。路图的概念是在1989年由Broersma和Hoede提出的。与(无向)图类似,Harary和Norman在1960年首先提出了有向线图的概念。最近Broersma和Li将(无向)路图和有向线图的概念推广到了有向路图。 本文主要研究路图及有向路图的同构问题。令Pk和Ck分别表示一条k个顶点的路和一个k个顶点的圈。∏k(G)表示G中所有k个顶点的路的集合(k≥1)。一个图G的路图Pk(G),其顶点集是∏k(G),而边是连接这样成对的顶点：在G中它们代表两条路Pk且这两条路的并是一条路Pk+1或一个圈Ck。有向路图可以类似地定义。令→Pk和→Ck分别表示一条k个顶点的有向路和一个k个顶点的有向圈。→∏k(D)表示有向图D中所有→Pk的集合。一个有向图D的有向路图→Pk(D),其顶点集是→∏k(D);pg是→Pk(D)的一条弧当且仅当在D中有一条有向路→Pk+1或一个有向圈→Ckv1v2…vk+1(当情况是→Ck时v1=vk+1)使得p=v1v2…vk和q=v2…vkvk+1。事实上,P2(G)和→P2(D)恰好分别是线图L(G)和有向线图→L(D)。 本论文由两部分组成。第一部分主要研究(无向)路图的同构问题,而第二部分主要研究有向路图的同构问题。 第一部分由第二,第三和第四章组成。在第二章中,我们主要考虑论文"Broersma and Hoede,Path graphs,J.Graph Theory 13(1989)427-444”中的一个公开问题,即是否存在一组三个互不同构的连通图但它们有同构的连通P3-图。我们证明了这样的三元组不存在。 对于一个图的变换,存在着一个普遍问题,即判定问题。对于Pk-变换,其判定问题是判定哪些图的Pk-图是给定的图。当k=2,3时,这个问题已经被完全解决了。对于线图,Whitney证明了K3和K1,3是唯一的一对其线图相同但本身并不同构的连通图。当k=3时,Aldred,Ellingham,Hemminger和Jipsen完全刻画了图的所有P3-同构,即具有同构P3-图的两个图或者同构,或者是三个特殊图类之一。当k=4时,Li和Zhao首先证明了对所有最小度至少是4的图,P4-变换是一一对应的,后来他们又证明了这个结果对最小度至少是3且满足另两个条件之一的图也成立。事实上,这两个结果仅对度数较高的图成立。在第三和第四章中,我们主要考虑P4-变换的判定问题。在第三章中,我们证明了对所有最小度至少是3的图,P4-变换是一一对应的,且除一族特殊图(标记为H)外,两个图之间的任意P4-同构都可以由其点同构导出。这个P4-图的结论与线图中Whitney的结论是十分相似的。同时这个结论也暗示了所有的非导出P4-同构只取决于最小度至多是3的图。 在第四章中,我们主要考虑两个图之间的非导出同构。除H这族图外,我们又发现了几对其P4-图同构但本身并不同构的连通图,还有大量的由两个最小度为1或者2的同构图产生的非导出的P4-同构。 第二部分是第五章,在这章中我们主要考虑有向→P3-图的判定问题,即判定哪些有向图的有向→P3-图是给定的有向图。唯一的结果是由Broersma和Li证明了具有同构有向→P3-图的两个有向图是“几乎”同构的。在这章中,首先我们对于有向图D引进了一个算子"C",它包含了D上的很多复杂运算但它仍然保持D的→P3-结构。然后,对于具有同构有向→P3-图的两个有向图,我们给出了一个充要条件。即如果有向图D和D'满足其有向→P3-图含有相同的孤立点个数,则→P3(D)同构于→P3(D')当且仅当C(D)同构于C(D')。这个结果说明了一个有向图可以被其有向→P3-图唯一确定,从而关于有向→P3-图的判定问题被彻底解决了。