20916.圖上關(guān)于點(diǎn)不交子圖的若干結(jié)果

1、SomeResuItsfbrVbrtexdisjointSubgraphsinGraphsAThesisSubmittedtoNingxiaUniversi哆inpartialmlflllmentoftherequirementforthedegreeofMasterOfScienceinOperatiOnResearChandCOntrOITheOrybyWULingXiU一DissertationSupervisor：Associa

2、teProfessorGaoY洫shuMa陀h，2015寧夏大學(xué)碩士學(xué)位論文中文摘要摘要圖論是一門近些年飛速發(fā)展的數(shù)學(xué)學(xué)科，它是組合數(shù)學(xué)的一個(gè)重要分支1736年歐拉發(fā)表了圖論的首篇文章解決了著名的哥尼斯堡七橋問題從19世紀(jì)中葉開始，圖論進(jìn)入第二個(gè)發(fā)展階段，這一時(shí)期，圖論問題大量出現(xiàn)，如地圖染色的四色問題、由“周游世界”游戲發(fā)展起來的哈密爾頓問題等進(jìn)入20世紀(jì)，隨著計(jì)算機(jī)科學(xué)的不斷發(fā)展，圖論在各個(gè)領(lǐng)域的廣泛應(yīng)用也越來越受到數(shù)學(xué)界和其他科學(xué)

3、界的重視本文僅考慮簡單、無向有限圖，這些圖不包含重邊以及環(huán)設(shè)G是一個(gè)圖，z和可是G中的兩個(gè)相異的頂點(diǎn)，口圖定義為三條內(nèi)不交的路的集合，這些路有相同的的起點(diǎn)和終點(diǎn)且起點(diǎn)和終點(diǎn)這兩個(gè)頂點(diǎn)是互異的樹指的是連通且不含圈的無向圖，生成樹是指包含了圖G的所有頂點(diǎn)的圖，且該圖是樹設(shè)乃和乃是G的兩個(gè)生成樹，如果對G的任意兩個(gè)頂點(diǎn)z和可，乃和乃中的z一可路是內(nèi)不交的，則稱乃和乃是G的兩個(gè)完全獨(dú)立的生成樹G的哈密爾頓圈是指包含了G的所有項(xiàng)點(diǎn)的圈本文主要考慮

4、了以下幾個(gè)問題：兩個(gè)完全獨(dú)立生成樹存在的度和條件，三個(gè)內(nèi)不交的臼圖的極值函數(shù)全文共有四章第一章介紹了圖的基本概念及所研究問題的歷史背景和發(fā)展情況第二章主要研究了三個(gè)內(nèi)不交的口圖的極值函數(shù)主要結(jié)論如下：任意頂點(diǎn)數(shù)n≥12，邊數(shù)至少為max『學(xué)]，I些嚳1]的圖包含三個(gè)內(nèi)不交的口圖第三章主要研究了兩個(gè)完全獨(dú)立生成樹的度和條件主要結(jié)論如下：頂點(diǎn)數(shù)n≥7的圖包含兩個(gè)完全獨(dú)立的生成樹。如果這個(gè)圖中的任意兩個(gè)不相鄰的頂點(diǎn)的度和至少為n最后，本文的每