English  |  正體中文  |  简体中文  |  全文笔数/总笔数 : 50123/85142 (59%)
造访人次 : 7906826      在线人数 : 56
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
搜寻范围 查询小技巧:
  • 您可在西文检索词汇前后加上"双引号",以获取较精准的检索结果
  • 若欲以作者姓名搜寻,建议至进阶搜寻限定作者字段,可获得较完整数据
  • 进阶搜寻


    jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/94013


    题名: C4飽和圖的探討
    其它题名: Study of C4 saturated graph
    作者: 洪明岳;Hung, Ming-Yueh
    贡献者: 淡江大學中等學校教師在職進修數學教學碩士學位班
    高金美
    关键词: 完全圖;完全多分圖;C4飽和圖;complete graph;complete multipartite graph;C4 saturated graph
    日期: 2013
    上传时间: 2014-01-23 13:47:37 (UTC+8)
    摘要: 假設圖G 並不包含子圖C4,若在圖G 中任意不相鄰的兩點增加一邊後,就
    會包含有子圖C4,那我們就稱圖G 為C4 飽和圖。令sat(n,C4)和ex(n,C4)分別代
    表所有n 點C4 飽和圖中的邊數最小值與最大值。
    在這篇論文中找到含有n 點C4 飽和圖的一種建構法,並給予含有n 點C4
    飽和圖最少邊的一種建構法。再利用當n<=11 時C4 飽和圖的邊數之上、下界,
    建構出其邊數介於sat(n,C4)和ex(n,C4)之間的n 點C4 飽和圖。接著應用圖的鄰接矩陣及C4 飽和圖的性質,利用Maple 判斷所產生的圖是否為C4 飽和圖。
    我們定義了在完全多分圖中的C4 飽和圖,並探討完全多分圖Kn(m)的C4 飽
    和圖中邊數最少的建構方式,得到以下結果:

    1. sat(Kn,m, C4) <= m + n - 1,其中sat(Kn,m, C4) = min {│E(G)│: 圖G 為Kn,m 中C4 飽和圖}。
    2. sat(Kn(m), C4) <= mn – 1 + ┌(n-2)/2┐*m, 其中sat(Kn(m), C4) = min {│E(G)│: 圖 G 為Kn(m) 中C4 飽和圖},┌x┐為大於等於x 的最小整數值。
    Let G be a graph. If there is no 4-cycle contained in G and connecting any non
    adjacent vertices of G will obtain a 4-cycle, then we call G is a C4 saturated graph.
    Let sat(n, C4) and ex(n, C4) be the minimum and maximum number of edges of all C4
    saturated graphs with n vertices, respectively.
    In this thesis, we obtain a construction of C4 saturated graph with n points, and
    give another construction of C4 saturated graph with minimum edge. For n <= 11, we give a C4 saturated graph with n vertices and q edges, for each q between sat(n, C4)
    and ex(n, C4). After that, we use Maple to check whether the graph is a C4 saturated graph by using the adjacency matrix of a graph and the properties of C4 saturated graphs.
    We define a C4 saturated graph in a complete multipartite graph Kn (m) and obtain the following results:

    1. sat(Kn,m, C4) <= m + n - 1; and
    2. sat(Kn(m), C4) <= mn – 1 + ┌(n-2)/2┐*m, where sat(K, C4) = min {|E(G)|: G is a C4 saturated graph in the graph K} and ┌x┐ is the smallest integer greater than x .
    DOI: 10.6846%2fTKU.2013.00406
    显示于类别:[數學學系暨研究所] 學位論文

    文件中的档案:

    档案 描述 大小格式浏览次数
    index.html0KbHTML155检视/开启
    index.html0KbHTML1检视/开启

    在機構典藏中所有的数据项都受到原著作权保护.

    TAIR相关文章

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