Kaavio (erillinen matematiikka) - Graph (discrete mathematics)

Kaavio, jossa on kuusi kärkeä ja seitsemän reunaa.

On matematiikka , ja tarkemmin sanoen graafiteoria , joka on graafinen esitys, on rakenne, jonka suuruus on joukko esineitä, joissa jotkut parit esineet ovat tietyssä mielessä "liittyvät". Esineet vastaavat matemaattisia abstraktioita kutsutaan kärkipisteet (kutsutaan myös solmut tai pisteiden ) ja kunkin niihin liittyvien parien pisteiden kutsutaan reuna (kutsutaan myös linkki tai linja ). Tyypillisesti kuvaaja kuvataan kaavamaisesti pisteiden tai ympyröiden joukkona pisteille, joita yhdistävät viivat tai käyrät reunoille. Kaaviot ovat yksi tutkimuksen kohteistadiskreetti matematiikka .

Reunat voivat olla suunnattuja tai suuntaamattomia. Esimerkiksi, jos kärkipisteet edustavat ihmisiä juhlissa ja kahden ihmisen välillä on reuna, jos he kättelevät toisiaan, tämä kuvaaja on suunnaton, koska kuka tahansa A voi kätellä henkilöä B vain, jos B myös kättelee A: ta . Sitä vastoin, jos jokin etu henkilöstä A henkilöön B vastaa A: ta, on velkaa B: lle , tämä kaavio on suunnattu, koska velkaa ei välttämättä vastine. Edellistä kaaviotyyppiä kutsutaan suunnattomaksi kuvaajaksi, kun taas jälkimmäistä graafia kutsutaan suunnatuksi kuvaajaksi .

Kaaviot ovat kuvaajan teorian tutkima perusaine . Sanaa "kuvaaja" käytti ensimmäisen kerran tässä mielessä JJ Sylvester vuonna 1878 suorassa suhteessa matematiikan ja kemiallisen rakenteen välillä (jota hän kutsui kemikografiseksi kuvaksi).

Määritelmät

Graafiteorian määritelmät vaihtelevat. Seuraavassa on joitain yksinkertaisempia tapoja määritellä kuvaajat ja niihin liittyvät matemaattiset rakenteet .

Kaavio

Kaavio, jossa on kolme kärkeä ja kolme reunaa.

Kaavio (joskus kutsutaan suuntaamattoman graafin erottaa siitä suunnattu graafi , tai yksinkertainen kaavio erottaa siitä multigraph ) on pari G = ( V , E ) , jossa V on joukko, jonka elementit kutsutaan kärkipisteet (yksikkö: Vertex), ja E on joukko paripisteitä, joiden elementtejä kutsutaan reunoiksi (joskus linkkeiksi tai viivoiksi ).

Reunan { x , y } pisteitä x ja y kutsutaan reunan päätepisteiksi . Reuna sanotaan liittymään x ja y ja olla tapahtuman päälle x ja y . Piste ei voi kuulua mihinkään reunaan, jolloin sitä ei yhdistetä mihinkään muuhun kärkeen.

Multigraph on yleistys, joka sallii useiden reunat on sama pari päätepisteiden. Joissakin teksteissä monikuvauksia kutsutaan yksinkertaisesti kaavioiksi.

Joskus kuvaajat voivat sisältää silmukoita , jotka ovat reunoja, jotka liittyvät pisteeseen itseensä. Silmukoiden sallimiseksi yllä olevaa määritelmää on muutettava määrittelemällä reunat kahden pisteen monisarjoina kahden joukon sijasta. Tällaisia ​​yleistettyjä kaavioita kutsutaan kuvaajaksi, jossa on silmukoita, tai yksinkertaisesti kuvaajaksi, kun asiayhteydestä käy selvästi ilmi, että silmukat ovat sallittuja.

Yleensä pistejoukon V oletetaan olevan äärellinen; tämä tarkoittaa sitä, että reunojen joukko on myös rajallinen. Ääretöntä kuvaajaa pidetään joskus, mutta sitä pidetään useammin erityisenä binäärisuhteena , koska useimmat äärellisten kaavioiden tulokset eivät ulotu äärettömään tapaukseen tai tarvitsevat melko erilaisen todistuksen.

Tyhjä kaavio on graafinen esitys, joka on tyhjä joukko solmuja (ja siten tyhjä joukko reunat). Järjestys kuvaajan on sen solmujen lukumäärä | V | . Koko kuvaajan on sen reunojen määrä | E | . Kuitenkin joissakin yhteyksissä, kuten algoritmien laskennallisen monimutkaisuuden ilmaisemisessa , koko on | V | + | E | (muuten ei-tyhjä kaavio voi olla kooltaan 0). Aste tai valenssi on kärki on määrä reunat osuvat siihen; silmukoilla varustetuille kaavioille silmukka lasketaan kahdesti.

Järjestyksessä n olevassa kaaviossa kunkin kärjen suurin aste on n - 1 (tai n, jos silmukat ovat sallittuja) ja reunojen enimmäismäärä on n ( n - 1)/2 (tai n ( n + 1)/ 2 jos silmukat ovat sallittuja).

Kaavion reunat määrittelevät symmetrisen suhteen pisteissä, jota kutsutaan vierekkäissuhteeksi . Erityisesti kaksi huippua x ja y ovat vierekkäin, jos { x , y } on reuna. Kaavio voi olla täysin määritellyt sen vierusmatriisiksi , joka on neliömatriisi, jossa ij määritellään yhteyksien määrä solmusta i solmuun j . Yksinkertainen kuvaaja, joka osoittaa katkaisun tai yhteyden vastaavasti (eli reuna ei voi alkaa ja päättyä samassa kärjessä). Kaavioille, joissa on silmukoita, on ominaista, että jotkut tai kaikki ovat yhtä kuin positiivinen kokonaisluku, ja monikuvaajalle (jossa on useita reunoja pisteiden välissä) on ominaista, että osa tai kaikki ovat yhtä kuin positiivinen kokonaisluku. Ohjaamattomissa kaavioissa on symmetrinen vierekkäismatriisi ( ).

Suunnattu kaavio

Suunnattu kuvaaja, jossa on kolme kärkeä ja neljä suunnattua reunaa (kaksoisnuoli edustaa reunaa kumpaankin suuntaan).

Suunnattu graafi tai suunnatun graafin on graafinen esitys, jossa reunat ovat suuntaviivoja.

Termin rajoitetussa mutta hyvin yleisessä merkityksessä suunnattu kuvaaja on pari, joka sisältää:

  • , Joka on asetettu ja pisteiden (kutsutaan myös solmut tai pistettä );
  • , Joka on joukko on reunat (kutsutaan myös ulottuvat reunat , suunnattuja linkkejä , suunnattu linjat , nuolet tai kaaria ), jotka on tilata paria solmujen (eli reuna on yhdistetty kaksi erillistä kärkipisteen).

Epäselvyyden välttämiseksi tämäntyyppistä objektia voidaan kutsua tarkasti suunnatuksi yksinkertaiseksi kuvaajaksi .

Reuna suunnattu kohteeseen , pisteiden ja kutsutaan päätepisteet reunan, hännän reunan ja pään reunan. Reuna sanotaan liittymään ja ja olla tapahtuman päälle ja . Piste voi olla kaaviossa eikä kuulu reunaan. Reuna kutsutaan käännetty reuna on . Useat reunat , jotka eivät ole sallittuja yllä olevan määritelmän mukaan, ovat kaksi tai useampia reunoja, joilla on sama häntä ja sama pää.

Useamman reunan sallivan termin yleisemmässä merkityksessä suunnattu kuvaaja on järjestetty kolminkertainen, joka sisältää:

  • , Joka on asetettu ja pisteiden (kutsutaan myös solmut tai pistettä );
  • , Joka on joukko on reunat (kutsutaan myös ulottuvat reunat , suunnattuja linkkejä , suunnattu linjat , nuolet tai kaaria );
  • , esiintyvyysfunktio, joka yhdistää jokaisen reunan tilattuun kärkipariin (eli reuna liittyy kahteen erilliseen pisteeseen).

Epäselvyyden välttämiseksi tämäntyyppistä objektia voidaan kutsua tarkasti suunnatuksi monikuvaajaksi .

Silmukka on reuna, joka liittyy kärkipiste itse. Kahdessa yllä olevassa määritelmässä määritellyillä suunnatuilla kuvaajalla ei voi olla silmukoita, koska kärkipisteen itseensä yhdistävä silmukka on reuna (suunnatulle yksinkertaiselle kuvaajalle) tai se tulee (suunnatulle monikuvaajalle), joka ei ole sisällä . Joten silmukoiden sallimiseksi määritelmiä on laajennettava. Suunnattujen yksinkertaisten kaavioiden määritelmä on muutettava muotoon . Suunnattujen monikuvausten määritelmä on muutettava muotoon . Epäselvyyden välttämiseksi tämäntyyppisiä objekteja voidaan kutsua täsmälleen suunnatuksi yksinkertaiseksi kuvaajaksi, joka sallii silmukoita, ja suunnatuksi monikuvaksi, joka sallii silmukat (tai värähtelyn ).

Reunat suunnatun yksinkertainen kaavio sallii silmukoita on homogeeninen suhteessa ~ on kärjet , jotka kutsutaan vierekkäisyys suhde on . Erityisesti kullekin reunalle sen päätepisteet ja sanotaan olevan vierekkäin , mikä on merkitty ~ .

Sekoitettu kaavio

Sekoitettu kaavio on graafinen esitys, jossa jotkin reunat voidaan ohjata, ja jotkut voivat olla suuntaamattomia. Se on tilattu kolminkertainen G = ( V , E , ) varten sekoitettu yksinkertainen kaavio ja G = ( V , E , , φ E , φ ) varten sekoitettu multigraph kanssa V , E (suuntaamattomassa reunat), (suunnatut reunat), ϕ E ja ϕ A kuten edellä on määritelty. Suunnatut ja suunnattomat kaaviot ovat erikoistapauksia.

Painotettu kuvaaja

Painotettu kuvaaja, jossa on kymmenen kärkeä ja kaksitoista reunaa.

Painotettu kaavio tai verkko on graafinen esitys, jossa numero (paino) on kullekin reunalle. Tällaiset painot voivat edustaa esimerkiksi kustannuksia, pituuksia tai kapasiteettia riippuen ongelmasta. Tällaisia ​​kaavioita syntyy monissa yhteyksissä, esimerkiksi lyhyimmän reitin ongelmissa , kuten matkustava myyjä -ongelma .

Kaavioiden tyypit

Suunnattu kaavio

Yksi suuntautuneen kuvaajan määritelmä on, että se on suunnattu kuvaaja, jossa enintään yksi ( x , y ) ja ( y , x ) voi olla kaavion reunoja. Toisin sanoen se on suunnattu kuvaaja, joka voidaan muodostaa suuntaamattoman (yksinkertaisen) kuvaajan suuntauksena .

Jotkut kirjoittajat käyttävät "suunnattua kuvaajaa" tarkoittamaan samaa kuin "suunnattu kuvaaja". Jotkut kirjoittajat käyttävät "suuntautunutta kuvaajaa" tarkoittamaan minkä tahansa suunnatun kaavion tai monikuvaajan suuntausta.

Säännöllinen kaavio

Säännöllinen graafi on kuvaaja, jossa jokainen kärki on sama määrä naapurit, eli joka kärkeen on yhtä paljon. Säännöllistä kuvaajaa, jonka kärjet ovat k, kutsutaan k -säännölliseksi kuvaajaksi tai asteen k säännölliseksi kuvaajaksi .

Täydellinen kaavio

Täydellinen kuvaaja, jossa on viisi kärkeä ja kymmenen reunaa. Jokaisella kärjellä on reuna kaikkiin muihin pisteisiin nähden.

Täydellinen kaavio on graafinen esitys, jossa kukin kärkipisteparin on liittynyt reuna. Täydellinen kaavio sisältää kaikki mahdolliset reunat.

Äärellinen kuvaaja

Äärellinen kaavio on graafinen esitys, jossa kärki asettaa ja reuna asettaa ovat äärelliset joukot . Muussa tapauksessa sitä kutsutaan äärettömäksi kuvaajaksi .

Yleisimmin graafiteoriassa oletetaan, että käsitellyt kuvaajat ovat äärellisiä. Jos kaaviot ovat rajattomat, se yleensä ilmoitetaan erikseen.

Yhdistetty kaavio

Ohjaamattomassa käyrässä järjestämätöntä kärkiparia { x , y } kutsutaan yhdistetyksi, jos polku johtaa x: stä y: hen . Muussa tapauksessa järjestämätöntä paria kutsutaan katkaistuksi .

Kytketty kaavio on suuntaamattoman graafin, jossa jokainen järjestyksetön pari graafin on kytketty. Muussa tapauksessa sitä kutsutaan katkaistuksi kuvaajaksi .

Suunnatussa kaaviossa järjestettyä kärkiparia ( x , y ) kutsutaan vahvasti kytketyksi, jos suunnattu polku johtaa x: stä y: hen . Muussa tapauksessa tilattua paria kutsutaan heikosti yhdistetyksi, jos suuntaamaton polku johtaa x: stä y: hen sen jälkeen, kun kaikki sen suunnatut reunat on korvattu suunnattomilla reunoilla. Muussa tapauksessa tilattua paria kutsutaan katkaistuksi .

Vahvasti kytketty kuvaaja on suunnattu graafi, jossa jokainen määräsi pari graafin on vahvasti kytketty. Muussa tapauksessa sitä kutsutaan heikosti yhdistetyksi kuvaajaksi, jos graafin jokainen järjestetty kärkipari on heikosti yhteydessä. Muussa tapauksessa sitä kutsutaan katkaistuksi kuvaajaksi .

K-kärki-kytketty kuvaajan tai k-reuna-kytketty kaavio on graafinen esitys, jossa ei joukko k - 1 kärkipisteet (vastaavasti, reunat) on olemassa, että kun se poistetaan, katkaisee kaavio. K -vertex-kytketty kuvaaja kutsutaan usein yksinkertaisesti k-kytketty kuvaaja .

Kaksipuolinen kuvaaja

Kaksijakoinen verkko on yksinkertainen kaavio, jossa kärki joukko voidaan jaettiin kahteen ryhmään, W ja X , niin että mitkään kaksi pisteiden W on yhteinen reuna, ei kaksi pisteiden X on yhteinen reuna. Vaihtoehtoisesti se on kuvaaja, jonka kromaattinen luku on 2.

On täydellinen kaksijakoinen kuvaaja , kärki joukko on unionin kahden erilliseen joukkoon, W ja X , niin että jokainen piste on W on lähellä jokaisen kärjen X , mutta ei ole reunoja sisällä W tai X .

Polkukaavio

Polku kaavio tai lineaarinen kuvaaja tilauksen n ≥ 2 on graafinen esitys, jossa solmut voidaan merkitä järjestyksessä v 1 , v 2 , ..., v n siten, että reunat ovat { v i , v i + 1 } , jossa i = 1, 2,…, n - 1. Polkukaavioita voidaan luonnehtia yhdistetyiksi kuvaajaiksi, joissa kaikkien muiden paitsi kahden pisteen aste on 2 ja kahden jäljellä olevan kärjen aste on 1. Jos reittikuvaaja esiintyy osakaaviona toisen kaavion, se on polku kyseisessä kaaviossa.

Tasomainen kaavio

Tasomainen kaavio on graafinen esitys, jonka kärjet ja reunat voidaan vetää tasossa siten, että mitkään kaksi reunojen leikkaavat.

Kierroskaavio

Sykli kaavio tai pyöreä kaavio järjestyksessä n ≥ 3 on graafinen esitys, jossa solmut voidaan merkitä järjestyksessä v 1 , v 2 , ..., v n siten, että reunat ovat { v i , v i + 1 } , jossa i = 1, 2,…, n - 1 sekä reuna { v n , v 1 } . Syklikaavioita voidaan luonnehtia yhdistetyiksi kuvaajaiksi, joissa kaikkien pisteiden aste on 2. Jos syklikaavio esiintyy toisen kuvaajan osakaaviona, se on sykli tai piiri tässä kuvaajalla.

Puu

Puu on suuntaamattoman graafin, jossa minkä tahansa kahden kärjet on yhdistetty täsmälleen yksi polku , tai vastaavasti liitetty asyklinen suuntaamattoman graafin.

Metsä on suuntaamattoman graafin, jossa mikä tahansa kaksi pistettä on yhdistetty enintään yksi polku, tai vastaavasti asyklinen suuntaamattoman graafin, tai vastaavasti disjoint liitto puita.

Polytree

Polytree (tai suunnattu puu tai suunnattu puu tai yksittäin kytketty verkkoon ) on suunnattu asyklinen kaavio (DAG), joiden kohde suuntaamattoman graafin on puu.

Polyforest (tai suunnattu metsä tai suunnattu metsä ) on suunnattu asyklinen kuvaajaan, jonka taustalla suuntaamattoman graafin on metsä.

Edistyneet luokat

Kehittyneempiä kaavioita ovat:

Kaavioiden ominaisuudet

Kaavion kahta reunaa kutsutaan vierekkäisiksi, jos niillä on yhteinen kärki. Suunnatun kuvaajan kahta reunaa kutsutaan peräkkäisiksi, jos ensimmäisen kärki on toisen pyrstö. Samoin kahta kärkeä kutsutaan vierekkäisiksi, jos niillä on yhteinen reuna ( peräkkäin, jos ensimmäinen on häntä ja toinen reunan pää), jolloin yhteisen reunan sanotaan liittyvän kahteen huippuun. Tämän reunan reunaa ja kärkeä kutsutaan tapahtumiksi .

Kaaviota, jossa on vain yksi kärki ja jossa ei ole reunoja, kutsutaan triviaaliksi kuvaajaksi . Graafi, jossa on vain kärkiä ja ilman reunoja, tunnetaan reunattomana kuvaajana . Graafia, jossa ei ole pisteitä ja reunoja, kutsutaan joskus nollagraafiksi tai tyhjäksi kuvaajaksi , mutta terminologia ei ole johdonmukainen, eivätkä kaikki matemaatikot salli tätä objektia.

Normaalisti kuvaajan kärkipisteet ovat luonteeltaan joukon elementtejä erottamiskykyisiä. Tällaista kuvaajaa voidaan kutsua kärkipisteeksi . Monissa kysymyksissä on kuitenkin parempi käsitellä kärkipisteitä erottamattomina. (Pisteet voidaan tietysti edelleen erottaa graafin ominaisuuksista, esim. Tulevien reunojen lukumäärästä.) Samat huomautukset pätevät myös reunoihin, joten graafisia, joilla on merkityt reunat, kutsutaan reunaleimattuiksi . Kaaviot, joissa on reunoihin tai kärkiin kiinnitettyjä tarroja, on yleisemmin merkitty tunnisteella . Näin ollen kuvaajaa, jossa kärkipisteitä ei voi erottaa ja reunoja ei voida erottaa, kutsutaan merkitsemättömiksi . (Kirjallisuudessa termi merkitty voi koskea myös muita merkintöjä sen lisäksi, että se erottaa vain eri kärjet tai reunat.)

Luokka Kaikkien kuvaajat on pilkku luokka Set ↓ D jossa D : Set → Set on functor ottaen joukko s ja s x s .

Esimerkkejä

Kaavio, jossa on kuusi kärkeä ja seitsemän reunaa.
  • Kaavio on kaavamainen esitys graafista, jossa on kärjet ja reunat
  • In Computer Science , suunnattuja graafeja käytetään edustamaan tietoa (esim käsitteellinen kaavio ), äärellistilaisia koneita , ja monia muita erillisiä rakenteita.
  • Binäärirelaatio R on joukko X määrittelee suunnattu graafi. Elementti x on X on suora edeltäjä elementin y on X , jos ja vain jos xRy .
  • Suunnattu kaavio voi mallintaa tietoverkkoja, kuten Twitteriä , ja yksi käyttäjä seuraa toista.
  • Erityisen säännöllisiä esimerkkejä suunnatuista kaavioista ovat äärellisesti muodostettujen ryhmien Cayleyn kaaviot sekä Schreier-kosetikaaviot
  • In luokassa Teoriassa jokainen pieni luokka on taustalla suunnattu multigraph jonka kärjet ovat esineitä luokan, ja jonka reunat ovat nuolet luokkaan. Kielellä luokan teoria, toinen sanoo, että on huonomuistinen functor alkaen luokasta pienet luokat on luokkaan vapisee .

Kaaviotoiminnot

On olemassa useita toimintoja, jotka tuottavat uusia kaavioita alkuperäisistä, jotka voidaan luokitella seuraaviin luokkiin:

Yleistykset

Vuonna hypergraph , reuna voi liittyä enemmän kuin kaksi pistettä.

Ohjaamatonta kuvaajaa voidaan pitää yksinkertaisena kompleksina, joka koostuu 1- yksinkertaisista (reunat) ja 0-yksinkertaisista (kärkipisteet). Kompleksit ovat sellaisinaan kaavioiden yleistyksiä, koska ne mahdollistavat korkeamman ulottuvuuden yksinkertaistamisen.

Jokaisesta kaaviosta syntyy matroidi .

Vuonna mallien teoria , kuvaaja on vain rakenne . Mutta siinä tapauksessa reunojen määrää ei ole rajoitettu: se voi olla mikä tahansa kardinaaliluku , katso jatkuva kaavio .

In laskennallinen biologia , teho kaavio analyysi tuo teho kuvaajat vaihtoehtona esitys suuntaamattoman kuvaajia.

Vuonna maantieteelliset tietojärjestelmät , geometrisia verkot ovat tiiviisti mallinnettu kaavioita, ja lainaa monia käsitteitä graafiteoria suorittamaan spatiaalianalyysi tiellä verkoissa tai apuohjelman ristikot.

Katso myös

Huomautuksia

Viitteet

Lue lisää

Ulkoiset linkit