20916.圖上關于點不交子圖的若干結(jié)果

1、SomeResuItsfbrVbrtexdisjointSubgraphsinGraphsAThesisSubmittedtoNingxiaUniversi哆inpartialmlflllmentoftherequirementforthedegreeofMasterOfScienceinOperatiOnResearChandCOntrOITheOrybyWULingXiU一DissertationSupervisor：Associa

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

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

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