Çizgelerin Sperner sayıları
Sperner number of graph
- Tez No: 259105
- Danışmanlar: DOÇ. DR. YUSUF CİVAN
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Çizge, Sperner say¬s¬, geren, ba¼g¬ms¬zl¬k say¬s¬.2009, 50 sayfa, Graph, Sperner number, realizer, independence number.2009, 50 pages
- Yıl: 2009
- Dil: Türkçe
- Üniversite: Süleyman Demirel Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 61
Özet
Dört bölümden olu¸san bu tezde Çizgelerin Sperner say¬lar¬tan¬t¬lm¬¸s ve incelenmi¸stir.Bu çal¬¸smaya gerekli olan baz¬temel Çizgeler teorisi ile ilgili tan¬mlarla giri¸s yap¬lm¬¸st¬r.·Ilk bölümde çal¬¸smam¬zla ilgili olan Milner¬n bir teoremine yer verilmi¸stir (Milner,1968). Bu çal¬¸smada Milner¬n bu teoreminin ·Ispat¬Scottdan al¬nm¬¸st¬r (Scott, 1999).·Ikinci bölümde arakesit çizgesi ve bir çizgenin Sperner say¬s¬tan¬t¬lm¬¸st¬r ve her sonluçizgenin bir Sperner say¬s¬oldu¼gu ispatlanm¬¸st¬r. Milner¬n teoremi yard¬m¬yla tam çiz-genin Sperner say¬s¬hesaplanm¬¸st¬r; ayr¬ca iki-çoklu çizgenin de Sperner say¬s¬buradaverilmi¸stir. Bir G çizgesinin verilen herhangi bir v kö¸sesi için vnin Sperner derecesitan¬t¬lm¬¸s ve vnin Sperner derecesi ile vnin kom¸suluklar¬n¬n indirgedi¼gi altçizgenintamsal örtüm say¬s¬aras¬ndaki ili¸skiyi veren bir teorem ispatlanm¬¸st¬r.Üçüncü bölümde, bu çal¬¸sma çizgelerin regüler gerenleriyle geni¸sletilmi¸stir ve regülerSperner say¬lar¬ tan¬mlanm¬¸st¬r. Verilen bir çizgenin bir k-regüler gereninin hangidurumlarda mevcut oldu¼gu incelenmi¸stir. Sperner say¬s¬ ile regüler Sperner say¬s¬aras¬nda ili¸skiye de¼ginilmi¸stir. Örnek olarak tam çizgenin ve tam iki-çoklu çizgeninregüler Sperner say¬lar¬hesaplanm¬¸st¬r.Son bölümde çizgelerin Sperner say¬lar¬için çe¸sitli s¬n¬rlar bulman¬n üzerinde durul-mu¸stur. ·Ilk önce bir çizgenin Sperner say¬s¬n¬n ba¼g¬ms¬zl¬k say¬s¬n¬n iki kat¬ndan dahabüyük veya e¸sit oldu¼gu ifade ve ispat edilmi¸stir. Ard¬ndan bu ifadenin e¸sitlik duru-muna bak¬lm¬¸st¬r; yani bir çizgenin Sperner say¬s¬n¬n, ba¼g¬ms¬zl¬k say¬s¬n¬n iki kat¬nae¸sit oldu¼gu durumlar incelenmi¸stir. Daha sonra da ba¼g¬ms¬zl¬k say¬s¬n¬n iki kat¬n-dan daha büyük oldu¼gu durumlara bak¬lm¬¸st¬r. Bunlar¬n ard¬nda ise bir çizgenin birkenar¬n¬n at¬lmas¬yla ve bir kenar¬n¬n büzülmesiyle Sperner say¬s¬n¬n nas¬l de¼gi¸siklikgösterdi¼gi incelenmi¸stir. Son olarak bir çizgenin Sperner say¬s¬ile bütünleyeninin kro-matik say¬s¬aras¬ndaki ili¸ski aç¬klanm¬¸s, bunun bir sonucu olarak bir çizgenin Spernersay¬s¬n¬n tamsal örtüm say¬s¬ndan daha büyük veya e¸sit oldu¼gu görülmü¸stür.
Özet (Çeviri)
In this thesis that consists of four chapters we introduce and study the Spernernumbers of graphs. We begin our work with providing some basic de nitions of graphtheory that are needed throughout our thesis.Apart from the common terminologies of graph theory, we supply some of the knownresults such as Milners theorem (Milner, 1968, Katona, 1998) that are related to ourwork in the rst chapter. The proof of Milners theorem that we state here is due toScott (Scott, 1999).The de nition of the Sperner number of a graph is given in the second chapter, wherewe also prove that it is well-de ned, that is, every nite graph has a Sperner number.We there compute the Sperner number of complete graphs (by use of Milners theorem)and complete bipartite graphs. For any given vertex v of a graph G, we introduce theSperner degree of v, and prove a theorem that relates the Sperner degree of v to theclique-covering number of the subgraph induced by the neighborhoods of v.In chapter three, we extend our work to include uniform realizers of graphs, and de nethe regular Sperner numbers. We investigate the existence of a k-regular realizer of agiven graph, and discuss the relation between k-regular Sperner numbers and ordinarySperner numbers of graphs. As examples, we compute k-regular Sperner numbers ofcomplete and complete bipartite graphs.The nal chapter is devoted to nd various bounds on the Sperner numbers of graphs.We prove that the Sperner number of a graph is bounded below by the twice of theindependence number of that graph. In the case of equality, we o¤er a detailed analysisof graphs satisfying this condition. Moreover, we also study those graphs such that thisbound is strict. We there also investigate how the Sperner number is e¤ected undersome graph operations, such as edge-contractions. Finally, we explain the relationbetween the Sperner number of a graph and the chromatic number of its complement.As a result, we prove that the Sperner number of a given graph is greater than or equalto the clique-covering number of the graph.
Benzer Tezler
- Distance spectra of graphs
Çizgelerin mesafe spektrumları
AHMET TUGAY KUZU
Yüksek Lisans
İngilizce
2021
MatematikGebze Teknik ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. AYSEL EREY
- Çizgelerin zedelenebilirlik değerlerinin bulunması üzerine
On finding vulnerability values of graphs
MUSTAFA ÇAĞATAY KÖRPE
Yüksek Lisans
Türkçe
2015
MatematikKarabük ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. TUFAN TURACI
- Çizgelerin diferansiyelinin hesaplanması
Computing the differential in graphs
AKIN KANLI
Yüksek Lisans
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
DOÇ. DR. ZEYNEP NİHAN BERBERLER
- Çizgelerin düzlemsel gösterilimlerinin elde edilmesi
Obtaining planar view of graphs
UĞUR ÖNER
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. VECDİ AYTAÇ