7,129
个编辑
更改
跳到导航
跳到搜索
第4行：
第4行： − +
无编辑摘要
==定义==
==定义==
设{{math|G {{=}} (V, E)}} 和 {{math|G′ {{=}} (V′, E′)}} 是两个图。若{{math|V′ ⊆ V}}且满足{{math|E′ ⊆ E ∩ (V′ × V′)}}）（即图{{math|G′ ⊆ G}}的所有边和点都属于图{{math|G}}）则称图{{math|G′ ⊆ G}}是图{{math|G}}的一个子图。若{{math|G′ ⊆ G}}，且对于顶点{{math|u}}、{{math|v}}及其连边，只要{{math|u}}和{{math|v}}存在于{{math|G′}}（即若{{math|U}}, {{math|V′ ⊆ V}}），那么{{math|G′ ⊆ G}}中就应该包含原图{{math|G}}中的所有{{math|u}}和{{math|V}}的对应连边（即{{math|⟨u, v⟩ ∈ E}}），则称此时图{{math|G′}}就是图{{math|G}}的导出子图。如果存在一个双射（一对一）{{math|f:V′ → V}}，且对所有{{math|u, v ∈ V′}}都有{{math|⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E}} ，则称{{math|G&prime }}是{{math|G}}的同构图（记作：{{math|G′ → G}}），映射f则称为{{math|G}}与{{math|G′}}之间的同构 isomorphism。<ref name="die1">{{cite journal |author=Diestel R |title=Graph Theory (Graduate Texts in Mathematics) |volume=173 |year=2005|publisher=New York: Springer-Verlag Heidelberg}}</ref>
设{{math|G {{=}} (V, E)}} 和 {{math|G′ {{=}} (V′, E′)}} 是两个图。若{{math|V′ ⊆ V}}且满足{{math|E′ ⊆ E ∩ (V′ × V′)}}）（即图{{math|G′ ⊆ G}}的所有边和点都属于图{{math|G}}）则称图{{math|G′ ⊆ G}}是图{{math|G}}的一个子图。若{{math|G′ ⊆ G}}，且对于顶点{{math|u}}、{{math|v}}及其连边，只要{{math|u}}和{{math|v}}存在于{{math|G′}}（即若{{math|U}}, {{math|V′ ⊆ V}}），那么{{math|G′ ⊆ G}}中就应该包含原图{{math|G}}中的所有{{math|u}}和{{math|V}}的对应连边（即{{math|⟨u, v⟩ ∈ E}}），则称此时图{{math|G′}}就是图{{math|G}}的导出子图。如果存在一个双射（一对一）{{math|f:V′ → V}}，且对所有{{math|u, v ∈ V′}}都有{{math|⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E}} ，则称{{math|G′}}是{{math|G}}的同构图（记作：{{math|G′ → G}}），映射f则称为{{math|G}}与{{math|G′}}之间的同构 isomorphism。<ref name="die1">{{cite journal |author=Diestel R |title=Graph Theory (Graduate Texts in Mathematics) |volume=173 |year=2005|publisher=New York: Springer-Verlag Heidelberg}}</ref>