在圖論中,圖G和H的字典序積（或合成圖）G ·H是一個(gè)圖,使得:G·H的頂點(diǎn)集是笛卡兒積V（G）×V（H）G· H中任何兩個(gè)頂點(diǎn)（u,v）和（x,y）相鄰當(dāng)且僅當(dāng)u與x在G中是相鄰的或u = x且v與y在H中是相鄰的。圖G的厚度t（G）是將G分解成不交的平面子圖的并的最少平面子圖數(shù)。確定任意圖的厚度是NP困難的,因此很難獲得一個(gè)圖的精確的厚度值。在本文中,我們將研究兩條不同路圖的字典序積的厚度以及路圖和完全圖的字典序積的厚度。第一章主要介紹圖的厚度的起源還有本文所需的一些基本知識。第二章主要通過引入平面圖及研究平面性的一些已知的結(jié)果。第三章主要介紹兩類特定的圖:圖運(yùn)算將應(yīng)用的路圖和完全圖。第四章主要介紹字典序積的基本結(jié)構(gòu),展示其他圖乘積的一些特殊性。在第五章主要研究兩條路圖的字典序積的厚度以及路圖和完全圖的字典序積的厚度。 

【文章來源】：湖南大學(xué)湖南省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：48 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 引言
    1.2 圖的基本概念
    1.3 本文的安排及主要工作
第2章 圖的平面性
    2.1 引言
    2.2 平面圖的歐拉公式
    2.3 可平面圖的表征或可平面性的標(biāo)準(zhǔn)
第3章 路圖與完全圖
    3.1 路圖
    3.2 完全圖
第4章 字典序積的基本結(jié)構(gòu)
    4.1 乘積的產(chǎn)類
    4.2 字典序積圖(或合成圖)
第5章 計(jì)算字典序積圖的厚度
    5.1 引言與定理
    5.2 兩路圖的字典序積的厚度或合成圖的厚度
    5.3 路圖和完全圖的字典序積的厚度或合成圖的厚度
結(jié)論
參考文獻(xiàn)
致謝



本文編號：3385427