Graad (grafentheorie)

ongerichte graaf waarin de graad van elke knoop is aangeduid
twee grafen met grafische lijst (3,2,2,2,2,1,1,1)

De graad of valentie van een knoop in een graaf is het aantal buren van die knoop. Grafen zijn het onderwerp van studie van de grafentheorie. De graad is in een niet-gerichte graaf dus het aantal bogen dat in de knoop samenkomt. Er wordt voor een gerichte graaf onderscheid gemaakt tussen de inkomende en de uitgaande graad, het aantal bogen dat in een knoop samenkomt en het aantal bogen dat vertrekt.

Een knoop met graad 0 is een geïsoleerde knoop. Een graaf waarin alle knopen dezelfde graad hebben is een reguliere graaf. Als die graad gelijk aan k is noemen we het een k-reguliere graaf. Een 3-reguliere graaf noemt men ook wel een kubieke graaf.

Grafische lijsten

De graden van alle knopen in een graaf, gerangschikt in een niet-stijgende rij, noemt men een grafische lijst, in het Engels graphic list, maar meer de degree sequence van de graaf. Er bestaan in het algemeen meer grafen met een verschillende topologie die dezelfde grafische lijst hebben, zoals hiernaast is geïllustreerd. Ieder van deze grafen noemt men een realisatie van de gegeven grafische lijst.

Niet iedere willekeurige niet-stijgende lijst van natuurlijke getallen is een grafische lijst. (3,3,3,1) is bijvoorbeeld geen grafische lijst: het is onmogelijk een graaf te maken waar dit de grafische lijst van is. De stelling van Erdős en Gallai geeft er een noodzakelijke en voldoende voorwaarde voor dat er gegeven een grafische lijst een graaf met die grafische lijst kan bestaan. Er bestaan verschillende bewijzen van deze stelling, waaronder een constructief bewijs waarin een graaf wordt geconstrueerd met de gegeven lijst als grafische lijst.[1]

Read other articles:

VisualEditor

Untuk penggunaan di Wikipedia bahasa Indonesia, Lihat Wikipedia:VisualEditor. VisualEditor TipeMediaWiki extension (en), Penyunting teks dan halaman duplikat permanen Wikimedia GenreWikiLisensilisensi MIT[1]Karakteristik teknisBahasa pemrogramanPHP Informasi pengembangPengembangWikimedia Foundation dan WikiaInformasi tambahanSitus webVisualEditor Sunting di Wikidata • L • B • Bantuan penggunaan templat ini VisualEditor (VE) adalah sebuah proyek MediaWiki untuk men...

 

 

Louis Jouvet

Louis JouvetLouis Jouvet di The School for Wives tahun 1950LahirJules Eugène Louis Jouvet24 December 1887Crozon, FranceMeninggal16 August 1951 (usia 63)Paris, PrancisPekerjaanAktor, Sutradara, Manajer TeaterSuami/istriElse Collin (1886–1967)Madeleine Ozeray (? – 1943) Jules Eugène Louis Jouvet (24 Desember 1887 – 16 Agustus 1951) adalah seorang aktor, sutradara teater dan pembuat film asal Prancis. Jouvet lahir di Crozon, Prancis 24 Desember 1887. Jouvet memiliki g...

 

 

ألتمار (نيويورك)

ألتمار الإحداثيات 43°30′42″N 76°00′02″W / 43.51167°N 76.00056°W / 43.51167; -76.00056   [1] تاريخ التأسيس 1813  تقسيم إداري  البلد الولايات المتحدة[2]  التقسيم الأعلى مقاطعة أوسويغو  خصائص جغرافية  المساحة 5.38675 كيلومتر مربع5.386749 كيلومتر مربع (1 أبريل 2010)  ارتفاع 17...

COVID-19 pandemic in London

Ongoing COVID-19 viral pandemic in London, England This article needs to be updated. Please help update this article to reflect recent events or newly available information. (September 2022) COVID-19 pandemic in LondonDiseaseCOVID-19Virus strainSARS-CoV-2LocationLondon, England, UKFirst outbreakWuhan, Hubei, ChinaArrival date12 February 2020Confirmed cases1,228,614[1][2] (up to 16 November 2021)Hospitalised cases1,094[3] (active, as of 15 November 2021)87,586[3]...

 

 

Élections cantonales de 2011 dans le Jura

2008 2015 Élections cantonales de 2011 dans le Jura 17 des 34 cantons du Jura 20 et 27 mars 2011 Type d’élection Élections cantonales Opposition départementale – Christophe Perny Liste PSDivers gauchePCF Sièges obtenus 19  2 Majorité départementale – Jean Raquin Liste UMPDVDPR Sièges obtenus 15  2 Président du Conseil général Sortant Élu Jean Raquin DVD Christophe Perny PS modifier - modifier le code - voir Wikidata  Les élections ca...

 

 

Dong District, Incheon

Autonomous District in Sudogwon, South KoreaDong 동구Autonomous DistrictKorean transcription(s) • Hanja東區 • Revised RomanizationDong-gu • McCune-ReischauerTong-guDong-gu district office in Incheon FlagCountrySouth KoreaRegionSudogwonProvincial levelIncheonAdministrative divisions11 dongsArea • Total7.19 km2 (2.78 sq mi)Population • Total75,513 • Density11,000/km2 (27,000/sq mi) • ...

Plinio Corrêa de Oliveira

Brazilian intellectual (1908–1995) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Plinio Corrêa de Oliveira – news · newspapers · books · scholar · JSTOR (September 2015) (Learn how and when to remove this message) Plinio Corrêa de OliveiraT.OCarmOliveira in a speech in 1942Born(1908-12-13)December 13, ...

 

 

Parkland High School (Pennsylvania)

Public high school in Allentown, Pennsylvania, United StatesParkland High SchoolParkland High School in March 2020Address2700 North Cedar Crest BoulevardAllentown, Pennsylvania 18104United StatesCoordinates40°38′20″N 75°32′47″W / 40.6388°N 75.5465°W / 40.6388; -75.5465InformationTypePublic high schoolEstablished1949School districtParkland School DistrictSuperintendentMark MadsonNCES School ID421851002829[1]PrincipalNathan DavidsonTeaching staff216....

 

 

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

西遊記大結局之仙履奇緣

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要編修，以確保文法、用詞、语气、格式、標點等使用恰当。 (2013年8月6日)請按照校對指引，幫助编辑這個條目。（幫助、討論） 此條目剧情、虛構用語或人物介紹过长过细，需清理无关故事主轴的细节、用語和角色介紹。 (2020年10月6日)劇情、用語和人物介紹都只是用於了解故事主軸，輔助�...

 

 

Vodacom

Vodacom Group LimitedJenisPublikKode emitenJSE: VODISINZAG000106063US92858D2009IndustriTelekomunikasiDidirikan1994; 30 tahun lalu (1994)PendiriTelkom South Africa: Alan Knott-Craig (Senior)KantorpusatMidrandWilayah operasiAfrikaTokohkunciShameel Joosub (CEO)Till Streichert (CFO)Dejan Kastelic (CTO)Phillip Moleketi (Ketua)ProdukTelepon selulerLayanan InternetPendapatanR86.370 miliar (US$6.48 miliar, 2018)R81.278 miliar (US$6.1 miliar, 2017)[1]Laba operasiR22.093 miliar (US$1.66 mi...

 

 

Al-Istibsar

Fourth hadith collection of the Four Books of Shia Islam Al-Istibsarالاستبصار Front cover of Al-IstibsarAuthorShaykh TusiLanguageArabicMedia typeBook Part of a series on Shia IslamTwelver Shi'ism The Fourteen Infallibles Muhammad Fatimah The Twelve Imams Ali Hasan Husayn al-Sajjad al-Baqir al-Sadiq al-Kazim ar-Rida al-Taqi al-Naqi al-Askari al-Mahdi Principles Monotheism Justice Prophethood Imamate Judgement Day Other beliefs Imamate of the Family Angels Mourning of Muharram Int...

Ioannis Kottounios

Greek scholar (17th century) Ioannis Kottounios (Ioannes Cottunius)Born1577 (1577)Veroia, Ottoman EmpireDied1658 (aged 80–81)Padua, Republic of VeniceAlma materCollegio Pontifico GrecoUniversity of PaduaEraRenaissanceRegionWestern philosophyInstitutionsCollegio Pontifico GrecoUniversity of PaduaUniversity of BolognaMain interestsMedicine, Greek literature, theology and philosophy Ioannis Kottounios (Greek: Ἰωάννης Κωττούνιος, Latin: Joannes Cottunius de ...

 

 

Mt Gravatt Bus Service

Mt Gravatt Bus ServiceMt Gravatt Bus Service Custom Coaches bodied Volvo B7RLE in January 2015Service areaSouth East BrisbaneService typeBus & coach operatorRoutes3HubsWestfield Mt GravattDepotsBurbankUnderwoodFleet48 (December 2022)[1]Websitewww.mtgcoach.com.au Mt Gravatt Bus Service is an Australian operator of bus services in South East Brisbane. It operates three services under contract to the Queensland Government under the Translink banner. History Originally named Burbank ...

 

 

USS LST-930

History United States NameLST-930 BuilderBethlehem-Hingham Shipyard, Hingham, Massachusetts Yard number3400[1] Laid down9 June 1944 Launched12 July 1944 Commissioned6 August 1944 Decommissioned26 June 1946 ReclassifiedLanding Ship Tank (Hospital), 15 September 1945 Stricken31 July 1946 Identification Hull symbol: LST-930 Hull symbol: LST(H)-930 Code letters: NVSF Honors andawards 2 × battle star FateSold for operation, 8 June 1948 General characteristics [2] Class and typeLS...

Self-checkout

Machine for customers to complete a retail transaction NCR Corporation model of self-service checkouts and fast-lane at a Sainsbury's store. NCR Corporation model of self-service checkout at an IKEA store. Self-checkouts (SCOs), also known as assisted checkouts (ACOs) or self-service checkouts, are machines that provide a mechanism for customers to complete their own transaction from a retailer without needing a traditional staffed checkout. When using SCOs, customers scan item barcodes befor...

 

 

Gaby

Disambiguazione – Se stai cercando altri significati, vedi Gaby (disambigua). Gabycomune(IT) Comune di Gaby(FR) Commune de Gaby Gaby – VedutaIl monumento ai caduti, il municipio e la scuola elementare LocalizzazioneStato Italia Regione Valle d'Aosta ProvinciaNon presente AmministrazioneSindacoFrancesco Valerio (lista civica Pour le Pays) dal 26-11-2018 Lingue ufficialiFrancese, italiano TerritorioCoordinate45°42′16″N 7°53′02″E45°42′16″N, 7°53′02″E...

 

 

Frozen (film 2013)

Frozen beralih ke halaman ini. Untuk film India tahun 2007 dengan judul yang sama, lihat Frozen (film 2007). FrozenPoster perilisan filmSutradara Chris Buck Jennifer Lee ProduserPeter Del VechoDitulis olehJennifer LeeCerita Chris Buck Jennifer Lee Shane Morris BerdasarkanThe Snow Queenoleh Hans Christian AndersenPemeran Kristen Bell Idina Menzel Jonathan Groff Josh Gad Santino Fontana Penata musikChristophe BeckSinematograferScott Beattie (perancang)Mohit Kallianpur (pencahayaan)Penyunt...

弗吉尼娅·韦德

弗吉尼娅·韦德出生Sarah Virginia Wade 1945年7月10日  （79歲）伯恩茅斯 就讀學校萨塞克斯大学塔尔波特西斯学校Tunbridge Wells Girls' Grammar School 職業網球運動員 獎項国际网球名人堂、大英帝國官佐勳章、Sarah Palfrey Danzig Award、BBC年度體壇風雲人物、大英帝國員佐勳章  弗吉尼娅·韦德（英語：Virginia Wade，1945年7月10日—），英国女子前网球运动员。 她曾获得...

 

 

ماريو دي أجاتا

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (ديسمبر 2015) ماريو دي أجاتا معلومات شخصية الميلاد 29 مايو 1926   أريتسو الوفاة 4 أبريل 2009 (82 سنة)   فلورنسا الطول 1.57 م (5 قدم 2 بوصة) الجنسية إيطالي الوزن وزن الديك �...