Kantengraph

Der Kantengraph oder Line-Graph ist ein Begriff aus der Graphentheorie. Er definiert zu einem gegebenen Graphen einen neuen Graphen, der durch die Vertauschung von Knoten und Kanten entsteht.

Definition

Der Kantengraph oder Line-Graph $L(G):=(V',E')$ eines einfachen Graphen $G=(V,E)$ ist in der Graphentheorie der Graph mit folgenden Eigenschaften:

$V'=E$ , das heißt, jede Kante von $G$ ist ein Knoten in $L(G)$ .
$E'=\left\{\left\{e_{1},e_{2}\right\}\mid |e_{1}\cap e_{2}|=1\right\}$ , das heißt, je zwei Knoten aus $V'$ sind in $L(G)$ adjazent, wenn die zugehörigen Kanten aus $E$ einen gemeinsamen Endknoten haben, also in $G$ adjazent sind.

Beispiel

Das folgende Beispiel veranschaulicht die Konstruktion des Kantengraphen $L(G)$ zu einem gegebenen Graphen $G=(V,E)$ . Der abgebildete Graph $G$ hat die Knotenmenge $V=\{1,2,3,4,5\}$ und die Kantenmenge $E=\{\{1,2\},\{1,3\},\{1,4\},\{2,5\},\{3,4\},\{4,5\}\}$ .

Aus dem Original $G$ wird jetzt ein neuer Graph konstruiert, indem jede Kante $e\in E$ von $G$ zu einem neuen Knoten $v'\in V'$ in $L(G)$ wird (durch die grüne Ellipse auf den originalen Kanten veranschaulicht). Die neu entstandenen Knoten werden genau dann miteinander verbunden, wenn die Kanten im Originalgraphen aneinanderstießen.

Das Resultat der Konstruktion erhält man durch Ausblenden des Originalgraphen $G$ . Zurück bleibt der Kantengraph $L(G)$ .

Wieder als Mengen ausgedrückt erhält man $L(G)=(V',\{\{\{1,2\},\{1,3\}\},\{\{1,2\},\{1,4\}\},\{\{1,2\},\{2,5\}\},\dots \})$ .

Eigenschaften

Der Kantengraph des Kreisgraphen $C_{n}$ ist isomorph zu seinem Ausgangsgraphen. Kreisgraphen (bzw. Graphen, deren sämtliche Komponenten Kreisgraphen sind) sind die einzigen Graphen mit dieser Eigenschaft.
Der Kantengraph des Sterngraphen $S_{n}$ ist der vollständige Graph $K_{n}$ .
Der Kantengraph eines bipartiten Graphen ist ein perfekter Graph.
Jeder Kantengraph besitzt eine Krausz-Partition.

Literatur

Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien / New York 1996, ISBN 3-211-82774-9, S. 180 ff.

Weblinks

Lutz Volkmann: Graphen an allen Ecken und Kanten. Skript 2006, S. 146ff (PDF; 3,51 MB)

Read other articles:

Ernst Thälmann

Ernst Thälmann Informasi pribadiLahir(1886-04-16)16 April 1886Hamburg, Kekaisaran JermanMeninggal18 Agustus 1944(1944-08-18) (umur 58)Kamp konsentrasi Buchenwald, Jerman NaziAnak1 putriPekerjaanPemimpin Partai Komunis Jerman (KPD)ProfesiRevolusioner, politikusKarier militerPihak Kekaisaran JermanMasa dinas1915–1918Pertempuran/perangPerang Dunia ISunting kotak info • L • B Ernst Johannes Fritz Thälmann (pelafalan dalam bahasa Jerman: [ɛʁnst ˈtɛːlman ...

Detasemen Khusus 81 (Penanggulangan Teror)

Satuan 81 KopassusDibentuk30 Juni 1982Negara IndonesiaCabang Angkatan Darat IndonesiaTipe unitSatuan AntiterorJumlah personelDirahasiakanBagian dariKopassusMarkasCijantung, Jakarta TimurJulukanSat-81 KopassusMotoSiap Setia BeraniPeralatanDirahasiakanSitus webwww.kopassus.mil.idTokohKomandanKolonel Inf. Nur Wahyudi, S.E., M.I.POl.Wadan— Satuan 81 Kopassus, atau dulu lebih dikenal sebagai SAT-81/Gultor adalah satuan antiteror di Kopassus setingkat Grup yang terdiri dari prajurit ter...

John Owen (theologian)

English theologian (1616–1683) John OwenBorn1616Stadhampton, Oxfordshire, EnglandDiedAugust 1683 (aged 66–67)Ealing, Middlesex, EnglandOccupation(s)Theologian, pastor, academic administratorNotable workCommunion with God The Mortification of Sin The Divine Power of the Gospel The Death of Death in the Death of ChristSpouseMary RookeTheological workEra17th centuryTradition or movementNonconformist Puritan Reformed theologyNotable ideasIndividual and distinct worship of each of the...

Norbert Ségard

Norbert Ségard Fonctions Ministre délégué auprès du Premier ministre 5 novembre 1980 – 1er février 1981(2 mois et 27 jours) Président Valéry Giscard d'Estaing Premier ministre Raymond Barre Gouvernement Barre III Secrétaire d’Etat aux Postes et Télécommunications 12 janvier 1976 – 5 novembre 1980(4 ans, 9 mois et 24 jours) Président Valéry Giscard d'Estaing Premier ministre Jacques ChiracRaymond Barre Gouvernement Chirac IBarre I, II et III Prédé...

Cinta Pertama (film 1973)

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Cinta Pertama film 1973 – berita · surat kabar · buku · cendekiawan · JSTOR Untuk kegunaan lain, lihat Cinta Pertama. Cinta PertamaSutradaraTeguh KaryaProduserSevihara SoedjarwoHatoek SoebrotoWiryo ...

Battle of Somosierra

1808 Battle of the Peninsular War in Spain For the 1936 battle, see Battle of Guadarrama. This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (May 2023) (Learn how and when to remove this template message) Battle of SomosierraPart of the Peninsular WarLa bataille de Somo-Sierra, 1810, Baron LejeuneDate30 November 1808LocationSomosierra Pass, Community of Madrid, S...

Brian Bruney

American baseball player (born 1982) Baseball player Brian BruneyBruney with the Washington NationalsPitcherBorn: (1982-02-17) February 17, 1982 (age 42)Astoria, Oregon, U.S.Batted: RightThrew: RightMLB debutMay 8, 2004, for the Arizona DiamondbacksLast MLB appearanceJune 24, 2012, for the Chicago White SoxMLB statisticsWin–loss record19–12Earned run average4.68Strikeouts252 Teams Arizona Diamondbacks (2004–2005) New York Yankees (2006–2009) Washingt...

1980

السنه دى بتوافق فى التقويمين القبطى والمصرى 1696(قبطى), 6221(مصرى) شوف احداث السنه مواليد وفيات مواليد 1980 وفيات 1980 الفيه: الفيه 2nd قرون: قرن 19th – قرن 20th – قرن 21st عقود: عقد 1960 عقد 1970 – عقد 1980 – عقد 1990 عقد 2000 سنين: 1978 1979 – 1980 – 1981 1982 1980 فى التقاويم التانيهتقويم ...

Kalikambal Temple

Temple in India Kālikāmbāl TempleKāligāmbāl Temple's Gopuram (Gateway tower) entrance.ReligionAffiliationHinduismDistrictChennaiDeityKāligāmbāl (Goddess Pārvathi)LocationLocationThambu Chetty Street, Parry's corner (Old: George Town), ChennaiStateTamil NaduCountryIndiaLocation in ChennaiGeographic coordinates13°05′40″N 80°17′21″E / 13.09455°N 80.2891°E / 13.09455; 80.2891ArchitectureTypeHindu temple architectureDate established1640Completed1678Tem...

2016 Winston-Salem mayoral election

Winston-Salem mayoral election, 2016 ← 2013 November 8, 2016 2020 → Nominee Allen Joines Party Democratic Popular vote 88,784 Percentage 94.07% Mayor before election Allen Joines Democratic Elected Mayor Allen Joines Democratic Elections in North Carolina Federal government U.S. President 1792 1796 1800 1804 1808 1812 1816 1820 1824 1828 1832 1836 1840 1844 1848 1852 1856 1860 1868 1872 1876 1880 1884 1888 1892 1896 1900 1904 1908 1912 1916 1920 1924 1928 19...

Marjorie Merriweather Post

American businesswoman (1887–1973) Marjorie Post redirects here. For the American actress Marjorie Armstrong Post, see Markie Post. Marjorie Merriweather PostPost in 1942Born(1887-03-15)March 15, 1887Springfield, Illinois, U.SDiedSeptember 12, 1973(1973-09-12) (aged 86)Washington, DC, U.S.Alma materMount Vernon Seminary and College (Washington, DC)OccupationsBusinesswomansocialitephilanthropistSpouses Edward Bennett Close (m. 1905; div. 191...

داود بن أبي هند دينار القشيري

داود بن أبي هند القشيري معلومات شخصية مكان الوفاة 139هـ ,ويقال 140 هـ الإقامة البصرة الكنية أبو محمد الخراساني , ويقال أبو بكر اللقب الإمام الحافظ الديانة الإسلام الحياة العملية المهنة عالم حديث اللغة الأم العربية اللغات العربية تعديل مصدري - تعديل الإمام الحافظ ال...

RAF Ascension Island

Military airfield in the Atlantic Ocean RAF Ascension Island Wideawake Airfield Ascension Island Auxiliary FieldNear Georgetown in Saint Helena, Ascension and Tristan da CunhaA Royal Air Force TriStar at RAF Ascension Island.Auxilium trans mare(Latin for 'Support across the Sea')RAF Ascension IslandLocation on Ascension IslandShow map of Ascension IslandRAF Ascension IslandRAF Ascension Island (South Atlantic)Show map of South AtlanticRAF Ascension IslandRAF Ascension Island (Atl...

ANSI/ISA-95

International manufacturing standardThis article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: ANSI/ISA-95 – news · newspapers · books · scholar · JSTOR (February 2024) (Learn how and when to remove this message)This article reads like a press release or a news article and may be largely based on routine coverage. Please help improve this article and add independe...

Sociocultural anthropology

Branch of anthropology Some of this article's listed sources may not be reliable. Please help improve this article by looking for better, more reliable sources. Unreliable citations may be challenged and removed. (November 2017) (Learn how and when to remove this message) Sociocultural anthropology is a term used to refer to social anthropology and cultural anthropology together. It is one of the four main branches of anthropology. Sociocultural anthropologists focus on the study of society a...

Skandal pelecehan seksual Johnny Kitagawa

Artikel ini perlu diterjemahkan ke bahasa Indonesia. Artikel ini ditulis atau diterjemahkan secara buruk dari Wikipedia bahasa selain Indonesia. Jika halaman ini ditujukan untuk komunitas berbahasa tersebut, halaman itu harus dikontribusikan ke Wikipedia bahasa tersebut. Lihat daftar bahasa Wikipedia. Artikel yang tidak diterjemahkan dapat dihapus secara cepat sesuai kriteria A2. Jika Anda ingin memeriksa artikel ini, Anda boleh menggunakan mesin penerjemah. Namun ingat, mohon tidak menyalin ...

Baja California Territory

Mexican territory from 1824-1853 and 1854-1931 For other uses of Baja California, see Baja California (disambiguation). 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: Baja California Territory – news · newspapers · books · scholar · JSTOR (February 2022) (Learn how and when to remove this message) Baja Cali...

Cheat Mountain

Cheat MountainView of US 33 crossing Cheat Mountain (in distance).Highest pointPeakThorny Flat, Pocahontas County, WVElevation4,848 ft (1,478 m)[1]Coordinates38°23′37″N 79°59′02″W / 38.39361°N 79.98389°W / 38.39361; -79.98389DimensionsLength50 mi (80 km)GeographyCheat MountainLocation of Cheat Mountain in West Virginia LocationCheat Mountain in Randolph County, WVCountryUnited StatesStateWest VirginiaCountiesPocahontas, ...

Alpay Özalan

Alpay ÖzalanNazionalità Turchia Altezza188 cm Calcio RuoloAllenatore (ex difensore) Termine carriera2008 - giocatore 2018 - allenatore CarrieraSquadre di club1 1992-1993 Altay23 (1)1993-1999 Beşiktaş148 (9)1999-2000 Fenerbahçe26 (3)2000-2003 Aston Villa52 (1)2004-2005 Incheon Utd10 (0)2005 Urawa Reds13 (0)2005-2008 Colonia48 (1) Nazionale 1995-2005 Turchia90 (4) Carriera da allenatore 2016-2017 Eskişehirspor2017-2018 Samsunspor2018 Turch...

Élections constituantes de 1946 dans la Mayenne

1945 1946 (II) Élections constituantes de 1946 dans la Mayenne le 2 juin 1946 Type d’élection Élection législative Postes à élire 4 députés modifier - modifier le code - voir Wikidata Les élections constituantes françaises de 1946 se tiennent le 2 juin. Ce sont les deuxièmes élections constituantes, après le rejet du Projet de constitution française du 19 avril 1946 lors du référendum du 5 mai. Mode de scrutin L'assemblée constituante est composée de 586 s...

/profillengkap.com/index.php/article/Bill Sellars

/profillengkap.com/index.php/article/Bangladeshi hip hop

Félix d'Herelle

Juan Bautista de Toledo

Bullying and emotional intelligence

Perdamaian melalui kekuatan

Roberto Roena