Fokszám (gráfelmélet)

A gráfelméletben egy gráfban egy csúcs fokszáma azoknak az éleknek a száma, amik illeszkednek a csúcsra. Egy csúcs fokszámának jele .

Irányítatlan gráfok

Irányítatlan gráf 6 csúccsal és 7 éllel.

Egy irányítatlan gráf egy csúcsának fokszáma a csúcsba befutó élek száma, úgy értve, hogy a hurokéleket kétszer számoljuk.

Az ábrán látható gráfhoz az alábbi fokszámok tartoznak:

Csúcs Fokszám
1 2
2 3
3 2
4 3
5 3
6 1

Fokszámösszeg-képlet, kézfogáslemma

Fokszámösszeg-képlet: Egy gráfban a fokszámok összege mindig páros, pontosabban az élek számának kétszerese.

Ennek következménye, hogy a páratlan fokú csúcsok száma páros (kézfogás-lemma).

Irányított gráf

Irányított gráf 4 csúccsal és 5 éllel.

Irányított gráfokban megkülönböztetjük a csúcsok kifokát és befokát: a kifok azt adja meg, hány él indul egy csúcsból, a befok pedig azt, hogy hány végződik benne.

A befok jele , a kifoké pedig .[1]

Az ábrán látható gráfhoz az alábbi fokszámok tartoznak:

Csúcs Befok Kifok
1 0 2
2 2 0
3 2 2
4 1 1

Irányított gráfban a befokok száma és a kifokok száma is egyenlő az élek számával.

Különleges fokszámértékek

Egy gráf egy csúcsát izolált csúcsnak nevezzük, ha a fokszáma nulla. Ha a fokszám egy, levélről beszélünk; ez a fogalom elsősorban fák kapcsán fordul elő, mivel egy legalább két csúcsú fának mindig van legalább két levele.

Ha egy irányított gráf egy csúcsának nulla a befoka, forrásnak, ha a kifoka nulla, nyelőnek nevezzük.

Ha egy gráf minden csúcsának fokszáma k, k-reguláris gráfnak hívjuk. Azt az összefüggő gráfot, aminek pontosan 0 vagy 2 páratlan fokszámú csúcsa van, Euler-gráfnak mondjuk. (Ezek pontosan azok a gráfok, amiket meg lehet rajzolni egyetlen vonallal.)

Fokszámsorozat

Két nem izomorf gráf, melynek ugyanaz a fokszámsorozata (3, 2, 2, 2, 2, 1, 1, 1).

A fokszámok sorozata egy gráf csúcsainak fokszámait tartalmazza nemnövekvő sorrendben (például d1 ≥ d2 ≥ … ≥ dn). Egy fokszámsorozat megvalósítható, ha van olyan gráf, melynek ez a fokszámsorozata. A fokszámok sorozata gráfinvariáns, tehát izomorf gráfoknak mindig ugyanaz lesz a fokszámsorozatuk. Viszont a fokszámsorozat nem azonosít egyértelműen egy gráfot, tehát, mint az ábrán látható esetben is, tartozhat nem izomorf gráfokhoz ugyanaz a sorozat.

Források

  1. ↑ Járai Antal. Bevezetés a matematikába, 3, Elte Eötvös Kiadó (2009). ISBN 9789632840772 

Read other articles:

Hodoyoshi 3

Hosted Payload Box installed on Hodoyoshi-3 & Hodooyshi-4 satellitesHodoyoshi-3 adalah mikro-satelit Jepang diluncurkan pada 2014. Satelit itu dibangun di bus 0.5x0.5x0.65m kotak-bentuk, dioptimalkan untuk peluncuran piggy-back. Semua instrumen yang didukung oleh sel surya yang dipasang di tubuh pesawat ruang angkasa dan dua sayap rintisan, dengan perkiraan daya listrik dari 50W. Referensi Lihat juga Hodoyoshi 4 Pranala luar Hodoyoshi 3-4 Satellite di Facebook Nano-Satellite Center, Unive...

 

Bandar Udara Internasional Montréal–Mirabel

Bandar Udara InternasionalMontréal–MirabelAéroport international Montréal–MirabelIATA: YMXICAO: CYMXInformasiJenisPublikPemilikTransport Canada[1]PengelolaAéroports de MontréalMelayaniMontreal RayaLokasiMirabel, QuebecDibuka04 Oktober 1975 (1975-10-04)Penerbangan komersial berakhir31 Oktober 2004 (2004-10-31)Zona waktuEST (UTC−05:00) • Musim panas (DST)EDT (UTC−04:00)Ketinggian dpl mdplKoordinat45°40′47″N 074°02′19″W / &#x...

 

GNU Hurd

Hurd beralih ke halaman ini. Untuk kegunaan lain, lihat Hurd (disambiguasi). Artikel ini terlalu bergantung pada referensi dari sumber primer. Mohon perbaiki artikel ini dengan menambahkan sumber sekunder atau tersier. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) GNU HurdDebian GNU HurdPerusahaan / pengembangProyek GNUThomas BushnellRoland McGrathMarcus BrinkmannNeal WalfieldDiprogram dalamAssembly, CKeluargabertipe UnixStatus terkiniSekarangModel sumberPerangkat L...

List of acts of the Parliament of the United Kingdom from 1931

Part of a series onBritish law Acts of Parliament of the United Kingdom Year      1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 ...

 

Gand-Wevelgem 2019

Gand-Wevelgem 2019 GénéralitésCourse81e Gand-WevelgemCompétitionUCI World Tour 2019 1.UWTDate31 mars 2019Distance251,5 kmPays Belgique FranceLieu de départDeinzeLieu d'arrivéeWevelgemÉquipes25Partants175Arrivants78Vitesse moyenne46,269 km/hSite officielSite officielRésultatsVainqueur Alexander Kristoff (UAE Team Emirates)Deuxième John Degenkolb (Trek-Segafredo)Troisième Oliver Naesen (AG2R La Mondiale) ◀20182020▶Documentation L'édition 2019 du Gand-Wevelgem in Flander...

 

Pendamping lokal desa

Pendamping lokal desa atau PLD adalah sebuah jabatan sebagai Pendamping desa di bawah Kementerian Desa, Pembangunan Daerah Tertinggal dan Transmigrasi Indonesia yang pembentukannya berdasarkan Undang-Undang Desa, yang bertugas untuk meningkatkan keberdayaan masyarakat dan sebagai fasilitator di sebuah desa. Sebuah ilustrasi suasana pelantikan Pendamping Lokal Desa di Jawa Tengah. Tugas Pendamping Lokal Desa No Tugas Pokok Langkah Kerja Output Kerja a) melakukan fasilitasi perencanaan pembangu...

Daftar Bupati Aceh Barat

Bupati Aceh BaratPetahanaDrs. Mahdi Efendi (Pj.)sejak 11 Oktober 2022KediamanPendopo Jalan Pocut BarenMasa jabatan5 tahun (definitif)Dibentuk1945Pejabat pertamaH. Ibnu Sa'danSitus webSitus Resmi Kabupaten Aceh Barat Berikut ini adalah daftar Bupati Aceh Barat dari masa ke masa. No Bupati Mulai menjabat Akhir menjabat Prd. Ket. Wakil Bupati 1 H.Ibnu Sa'dan 20 Oktober 1945 15 Juni 1947 1 2 Abdul Wahab 15 Juni 1947 22 September 1948 2 3 Abdul Gafur Akhir 7 Agustus 1957 28 Agustus 1958 3 4 T...

 

Deodoro da Fonseca

Manuel Deodoro da Fonseca Presiden Brasil ke-1Masa jabatan26 Februari 1891 (Kepala Pemerintahan Sementara sejak 15 November 1889) – 23 November 1891Wakil PresidenFloriano PeixotoPendahuluPedro II (sebagai Kaisar Brasil)PenggantiFloriano Peixoto Informasi pribadiLahirManuel Deodoro da Fonseca(1827-08-05)5 Agustus 1827Vila Madalena (now Marechal Deodoro), Alagoas, BrasilMeninggal23 Agustus 1892(1892-08-23) (umur 65)Barra Mansa, Rio de Janeiro, BrasilKebangsaanBrasilPartai politi...

 

Pugo, La Union

Peta menunjukan lokasi Pugo Data sensus penduduk di Pugo Tahun Populasi Persentase 199512.180—200013.4422.14%200718.2654.32% Pugo adalah munisipalitas yang terletak di provinsi La Union, Filipina. Pada tahun 2010, munisipalitas ini memiliki populasi sebesar 18.265 jiwa atau 3.588 rumah tangga. Pembagian wilayah Secara administratif Pugo terbagi menjadi 14 barangay, yaitu: Ambalite Ambangonan Cares Cuenca Duplas Maoasoas Norte Maoasoas Sur Palina Poblacion East San Luis Saytan Tavora East Ta...

Clare Gerada

London based general practitioner DameClare GeradaDBE FRCP FRCPsych FRCGPGerada in 2011BornClare Mary Louise Francis GeradaNovember 1959 (age 64)NigeriaCitizenshipBritish and MalteseEducationMB BS, 1983, UCL Medical SchoolOccupationGeneral practitionerKnown forChairperson of RCGPSpouseSimon WesselyChildren2Medical careerProfessionMedical doctorSub-specialtiesMental health (especially of health care workers), substance misuse, and problem gambling Dame Clare Mary Lou...

 

Ellehammer helicopter

Experimental Danish aircraft, 1912 Helicopter 1914 photo of Ellehammer's coaxial helicopter hovering Role Experimental helicopterType of aircraft Manufacturer Jacob Ellehammer Designer Jacob Ellehammer First flight 28 September 1912 Number built 1 The Ellehammer helicopter was an otherwise-unnamed experimental aircraft built in Denmark in 1912. Based on experiments with models, Jacob Ellehammer constructed a full-size machine equipped with two contra-rotating discs, each of which was fitted w...

 

Cinema of Australia

Film and television industry in Australia Cinema of AustraliaNo. of screens2,210 (2017)[1] • Per capita10.1 per 100,000 (2017)[1]Main distributorsVillage Roadshow/Warner Bros. (26.0%)Paramount (19.0%)20th Century Studios (Disney) (12.0%)[2]Produced feature films (2017)[1]Total55Fictional35 (63.6%)Animated0 (0%)Documentary20 (32.7%) This article is part of a series on theCulture of Australia Society History Language People Immigration Multicultu...

تجربة إيفري ومكلاود ومكارتي

استعمل إيفري ومكلاود ومكارتي سلاسلا من الحمض النووي الريبوزي منزوع الأكسجين المُنقّح مشابهة لهذه، ومُترسّبة عن محاليل مكونات الخلية، وذلك لإجراء تحوُّلات بكتيرية. تجربة إيفري ومَكلاود ومَكارتي برهنة تجريببة قام بها آزوُولد إيفري وكولن مكلاود وماكلن مكارتي سنة 1944، لإثب�...

 

Alberto Moreno (calciatore)

Alberto MorenoAlberto Moreno con la maglia del Siviglia nel 2013.Nazionalità Spagna Altezza172 cm Peso64 kg Calcio RuoloDifensore, centrocampista Squadra Villarreal CarrieraGiovanili 2010-2012 Siviglia Squadre di club1 2010-2013 Siviglia Atlético49 (6)2011-2014 Siviglia45 (3)2014-2019 Liverpool90 (3)2019- Villarreal98 (5) Nazionale 2012-2014 Spagna U-2110 (0)2013-2017 Spagna4 (0) Palmarès  Europei di calcio Under-21 OroIsraele 2013 1 I due numeri ind...

 

Pytheas

Pytheas dari MassaliaPatung Pytheas di luar Palais de la Bourse, Marseilles.Lahirskt. 350 SMMassaliaMeninggalskt. 285 SMKebangsaanYunaniWarga negaraMassalioteDikenal atasPelayaran terawal ke Inggris, Laut Baltik, dan Lingkar Arktik yang memiliki catatan, penulis Periplus.Karier ilmiahBidangGeografi, penjelajah, navigasiMenginspirasiahli geografi dan penjelajah klasik berikutnya Pytheas dari Massalia (Yunani Kuno: Πυθέας ὁ Μασσαλιώτης Pythéas ho Massaliōtes; Bahasa Latin:...

Area code 603

Telephone area code for all of New Hampshire Area code 603 in a 1956 map, covering the whole state. Area code 603 is the sole area code for the U.S. state of New Hampshire in the North American Numbering Plan (NANP). It was created as one of the original 86 numbering plan areas in October 1947. In 2011, area code 603 was said to be nearing exhaustion and a second area code for New Hampshire was expected to be activated by 2013 as a statewide overlay plan.[1] As a result of changes in ...

 

Gouhenans

Commune in Bourgogne-Franche-Comté, FranceGouhenansCommuneA general view of Gouhenans Coat of armsLocation of Gouhenans GouhenansShow map of FranceGouhenansShow map of Bourgogne-Franche-ComtéCoordinates: 47°36′28″N 6°28′12″E / 47.6078°N 6.47°E / 47.6078; 6.47CountryFranceRegionBourgogne-Franche-ComtéDepartmentHaute-SaôneArrondissementLureCantonVillersexelArea18.45 km2 (3.26 sq mi)Population (2021)[1]364 • Density4...

 

Pontmain

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (novembre 2009). Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes. Pontmain La basilique Notre-Dame-de-Pontmain. Bla...

Valganna (valle)

ValgannaVeduta del Lago di GannaStati Italia Regioni Lombardia Province Varese Località principaliValganna, Induno Olona, Cunardo FiumeMargorabbia; Olona Nome abitantivalgannesi Modifica dati su Wikidata · Manuale La Valganna è una valle della Provincia di Varese. Fa parte della Comunità Montana del Piambello. Indice 1 Geografia 1.1 Orografia 1.2 Idrografia 1.3 Le Grotte 2 Clima 2.1 Sport invernali 3 Voci correlate Geografia La valle inizia a nord di Varese, nella zona...

 

Tribunal pour enfants

Naples 1948. Garçon devant le tribunal du tribunal pour enfants de la maison de correction Albergo dei Poveri. Des prostituées, des vagabonds et des voleurs y étaient également envoyés par le tribunal pour enfants de Naples et enseignaient la broderie par des religieuses catholiques. La surpopulation et la misère ont aggravé le problème de la délinquance juvénile, qui s’est aggravé dans la plupart des pays en raison de la guerre et des conséquences des mauvaises conditions de vi...