377
个编辑
更改
跳到导航
跳到搜索
第23行：
第23行： − +
→Definition
Let {{math|G {{=}} (V, E)}} and {{math|G′ {{=}} (V′, E′)}} be two graphs. Graph {{math|G′}} is a ''sub-graph'' of graph {{math|G}} (written as {{math|G′ ⊆ G}}) if {{math|V′ ⊆ V}} and {{math|E′ ⊆ E ∩ (V′ × V′)}}. If {{math|G′ ⊆ G}} and {{math|G′}} contains all of the edges {{math|⟨u, v⟩ ∈ E}} with {{math|u, v ∈ V′}}, then {{math|G′}} is an ''induced sub-graph'' of {{math|G}}. We call {{math|G′}} and {{math|G}} isomorphic (written as {{math|G′ ↔ G}}), if there exists a bijection (one-to-one) {{math|f:V′ → V}} with {{math|⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E}} for all {{math|u, v ∈ V′}}. The mapping {{math|f}} is called an isomorphism between {{math|G}} and {{math|G′}}.<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>
Let {{math|G {{=}} (V, E)}} and {{math|G′ {{=}} (V′, E′)}} be two graphs. Graph {{math|G′}} is a ''sub-graph'' of graph {{math|G}} (written as {{math|G′ ⊆ G}}) if {{math|V′ ⊆ V}} and {{math|E′ ⊆ E ∩ (V′ × V′)}}. If {{math|G′ ⊆ G}} and {{math|G′}} contains all of the edges {{math|⟨u, v⟩ ∈ E}} with {{math|u, v ∈ V′}}, then {{math|G′}} is an ''induced sub-graph'' of {{math|G}}. We call {{math|G′}} and {{math|G}} isomorphic (written as {{math|G′ ↔ G}}), if there exists a bijection (one-to-one) {{math|f:V′ → V}} with {{math|⟨u, v⟩ ∈ E′ ⇔ ⟨f(u), f(v)⟩ ∈ E}} for all {{math|u, v ∈ V′}}. The mapping {{math|f}} is called an isomorphism between {{math|G}} and {{math|G′}}.<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 {{=}} (V, E)}} 和 {{math|G′ {{=}} (V′, E′)}} 是两个图。若{{math|V′ ⊆ V}}且满足{{math|E′ ⊆ E ∩ (V′ × V′)}}）（即图{{math|G′ ⊆ G}的所有边和点都属于图{{math|G}}）则称图{{math|G′ ⊆ G}是图{{math|G}}的一个子图<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′ ⊆ 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|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}}的导出子图。