English  |  正體中文  |  简体中文  |  Items with full text/Total items : 62797/95867 (66%)
Visitors : 3728055      Online Users : 866
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/87449


    Title: 完全圖分割成迴圈與星圖的探討
    Other Titles: Decomposition of complete graphs into cycles and stars
    Authors: 黃建華;Huang, Chien-Hua
    Contributors: 淡江大學數學學系碩士班
    高金美;Kau, Chin-Mei
    Keywords: 完全圖;迴圈;星圖;分割;complete graph;cycle;STAR;decomposition
    Date: 2013
    Issue Date: 2013-04-13 11:07:27 (UTC+8)
    Abstract: 一個具有n個點的圖中,若任意兩點皆有邊相連,我們稱此圖為n個點的完全圖,記作Kn。一個具有n個點的連通圖,其每一點的度數皆為2,我們稱此圖為n-迴圈,記作Cn。一個具有n+1個點的連通圖,其中有一點的度數為n,其餘各點的度數皆為1,我們稱此圖為星圖,記作Sn,同構於K1,n。設G為一個簡單圖,G1,G2,…,Gt為G的子圖,若滿足下列條件:
    (1) E(G1)∪E(G2)∪ ... ∪E(Gt) = E(G);
    (2) 對於1 ≦ i ≠ j ≦ t,E(Gi) ∩ E(Gj) = 空集合,
    則稱G可分割為G1,G2,…,Gt,記作G = G1+ G2+ … + Gt。若H是G的子圖,且G1,G2,…,Gt都與H同構,則稱G可分割成t個H,記為G = tH。若G可分割成p個G1與q個G2,則記為G = pG1 + qG2。 
    在本論文中,我們證明了:
    (1) 當n≡0 (mod 6),Kn可分割成C3和S3的各種組合。
    (2) 當n≡1 (mod 6),Kn可分割成C3和S3的各種組合。
    進而得到以下定理
    定理:當n≡1,3 (mod 6),n ≧ 3且p、q為非負整數。
    如果Kn可分割成p個C3和q個S3,
    若且唯若p + q = n(n-1)/6 且q ≠ 1,2。
    A complete graph Kn is a graph with n vertices and there is an edge joining any two vertices. An n-cycle Cn is a connected graph with n vertices and the degree of each vertex is 2. A star graph Sn is a graph with n+1 vertices and there is a vertex of degree n, the others are degree of 1. Let G be a simple graph and G1,G2,…,Gt be subgraphs of G. If E(G1)∪E(G2)∪…∪E(Gt) = E(G) and for all 1≦ i ≠ j ≦t,E(Gi)∩E(Gj) = empty set, then we call that G can be decomposed into G1, G2, … , Gt, denoted by G = G1+ G2+ … + Gt. If G1, G2, … , Gt are isomorphic to graph H, then we call G can be decomposed into H. If G can be decomposed into p copies of G1 and q copies of G2, that G can denoted by G = pG1 + qG2.
    In this paper, we show that:
    (1) if n≡1 (mod 6), then Kn can be decomposed into C3 and S3.
    (2) if n≡3 (mod 6), then Kn can be decomposed into C3 and S3.
    Combining the above results, we obtain the following theorem:
    Theorem: n≡1, 3 (mod 6), n≧3. For any nonnegative integers p and q.
    Kn can be decomposed into p copies of C3 and q copies of S3
    if and only if p + q = n(n-1)/6 and q ≠ 1, 2。
    Appears in Collections:[Graduate Institute & Department of Mathematics] Thesis

    Files in This Item:

    File SizeFormat
    index.html0KbHTML168View/Open

    All items in 機構典藏 are protected by copyright, with all rights reserved.


    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback