更改

跳到导航 跳到搜索
添加179字节 、 2020年5月6日 (三) 19:17
第23行: 第23行:  
Let {{math|G {{=}} (V, E)}} and {{math|G&prime; {{=}} (V&prime;, E&prime;)}} be two graphs. Graph {{math|G&prime;}} is a ''sub-graph'' of graph {{math|G}} (written as {{math|G&prime; ⊆ G}}) if {{math|V&prime; ⊆ V}} and {{math|E&prime; ⊆ E ∩ (V&prime; &times; V&prime;)}}. If {{math|G&prime; ⊆ G}} and {{math|G&prime;}} contains all of the edges  {{math|&lang;u, v&rang; ∈ E}} with {{math|u, v ∈ V&prime;}}, then {{math|G&prime;}} is an ''induced sub-graph'' of {{math|G}}. We call {{math|G&prime;}} and {{math|G}} isomorphic (written as {{math|G&prime; ↔ G}}), if there exists a bijection (one-to-one) {{math|f:V&prime; → V}} with  {{math|&lang;u, v&rang; ∈ E&prime; ⇔ &lang;f(u), f(v)&rang; ∈ E}} for all {{math|u, v ∈ V&prime;}}. The mapping {{math|f}} is called an isomorphism between {{math|G}} and {{math|G&prime;}}.<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&prime; {{=}} (V&prime;, E&prime;)}} be two graphs. Graph {{math|G&prime;}} is a ''sub-graph'' of graph {{math|G}} (written as {{math|G&prime; ⊆ G}}) if {{math|V&prime; ⊆ V}} and {{math|E&prime; ⊆ E ∩ (V&prime; &times; V&prime;)}}. If {{math|G&prime; ⊆ G}} and {{math|G&prime;}} contains all of the edges  {{math|&lang;u, v&rang; ∈ E}} with {{math|u, v ∈ V&prime;}}, then {{math|G&prime;}} is an ''induced sub-graph'' of {{math|G}}. We call {{math|G&prime;}} and {{math|G}} isomorphic (written as {{math|G&prime; ↔ G}}), if there exists a bijection (one-to-one) {{math|f:V&prime; → V}} with  {{math|&lang;u, v&rang; ∈ E&prime; ⇔ &lang;f(u), f(v)&rang; ∈ E}} for all {{math|u, v ∈ V&prime;}}. The mapping {{math|f}} is called an isomorphism between {{math|G}} and {{math|G&prime;}}.<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&prime; {{=}} (V&prime;, E&prime;)}} 是两个图。若{{math|V&prime; ⊆ V}}且满足{{math|E&prime; ⊆ E ∩ (V&prime; &times; V&prime;)}})(即图{{math|G&prime; ⊆ G}的所有边和点都属于图{{math|G}})则称图{{math|G&prime; ⊆ G}是图{{math|G}}的一个子图
+
设{{math|G {{=}} (V, E)}} 和 {{math|G&prime; {{=}} (V&prime;, E&prime;)}} 是两个图。若{{math|V&prime; ⊆ V}}且满足{{math|E&prime; ⊆ E ∩ (V&prime; &times; V&prime;)}})(即图{{math|G&prime; ⊆ G}的所有边和点都属于图{{math|G}})则称图{{math|G&prime; ⊆ 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&prime; ⊆ G}},且对于顶点{{math|u}}、{{math|v}}及其连边,只要{{math|u}}和{{math|v}}存在于{{math|G&prime;}}(即若{{math|U}}, {{math|V&prime; ⊆ V}}),那么{{math|G&prime; ⊆ G}}中就应该包含原图{{math|G}}中的所有{{math|u}}和{{math|V}}的对应连边(即{{math|&lang;u, v&rang; ∈ E}}),则称此时图{{math|G&prime;}}就是图{{math|G}}的导出子图。
 
若{{math|G&prime; ⊆ G}},且对于顶点{{math|u}}、{{math|v}}及其连边,只要{{math|u}}和{{math|v}}存在于{{math|G&prime;}}(即若{{math|U}}, {{math|V&prime; ⊆ V}}),那么{{math|G&prime; ⊆ G}}中就应该包含原图{{math|G}}中的所有{{math|u}}和{{math|V}}的对应连边(即{{math|&lang;u, v&rang; ∈ E}}),则称此时图{{math|G&prime;}}就是图{{math|G}}的导出子图。
377

个编辑

导航菜单