Inhoudsopgave
15 relaties: Algoritme, Beslissingsprobleem, Bio-informatica, Coenraad Bron, Complementgraaf, Deelverzameling, Grafentheorie, Kleuren van grafen, Kliek, NP-moeilijk, NP-volledig, Onafhankelijke verzameling, Overdekking (topologie), Perfecte graaf, Polynomiale tijd.
Algoritme
Algoritme om een willekeurig veelvlak in driehoeken op te delen (in het algemeen heeft dit probleem meerdere oplossingen, de bereikte oplossing hangt dus af van het gebruikte algoritme) Een algoritme is een stappenplan bestaande uit een set regels in vaste volgorde om tot een oplossing te komen en het einddoel te bereiken.
Bekijken Clique (grafentheorie) en Algoritme
Beslissingsprobleem
In de berekenbaarheids- en complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat, afhankelijk van de gegeven invoer, met 'ja' of 'nee' beantwoord dient te worden.
Bekijken Clique (grafentheorie) en Beslissingsprobleem
Bio-informatica
NCBI-website). De samenstelling van het menselijk genoom is een van de grootste prestaties van de bio-informatica. Bio-informatica is de wetenschap die tot doel heeft de biologische kennis te verrijken door kennis uit de informatica toe te passen op biologische data.
Bekijken Clique (grafentheorie) en Bio-informatica
Coenraad Bron
Coenraad Bron Coenraad Bron (Amsterdam, 2 augustus 1937 – Assen, 15 augustus 2006) was een Nederlandse informaticus.
Bekijken Clique (grafentheorie) en Coenraad Bron
Complementgraaf
Graaf met complementgraaf In de grafentheorie is de complementgraaf van een enkelvoudige graaf G weer een enkelvoudige graaf H, met dezelfde knopen als G waarin een zijde voorkomt dan en slechts dan als die niet in G voorkomt.
Bekijken Clique (grafentheorie) en Complementgraaf
Deelverzameling
Een venndiagram van de verzameling A als deelverzameling van B.B omvat A. In de verzamelingenleer is een deelverzameling van een gegeven verzameling een verzameling die geheel bevat is in (deel is van) de gegeven verzameling.
Bekijken Clique (grafentheorie) en Deelverzameling
Grafentheorie
Enkelvoudige graaf met zes knopen De grafentheorie is een deelgebied van de wiskunde dat de eigenschappen van grafen bestudeert.
Bekijken Clique (grafentheorie) en Grafentheorie
Kleuren van grafen
de Petersen-graaf. Het kleuren van grafen is een concept uit de grafentheorie, waarbij men in een niet-gerichte simpele graaf, bestaande uit knopen (vertices, V) die verbonden zijn door kanten (edges, E), aan elke knoop of kant een "kleur" toekent.
Bekijken Clique (grafentheorie) en Kleuren van grafen
Kliek
Een kliek of clique is een kleine informele groep.
Bekijken Clique (grafentheorie) en Kliek
NP-moeilijk
NP-moeilijk is een complexiteitsgraad.
Bekijken Clique (grafentheorie) en NP-moeilijk
NP-volledig
NP-volledigheid is een concept uit de complexiteitstheorie.
Bekijken Clique (grafentheorie) en NP-volledig
Onafhankelijke verzameling
In deze graaf vormen de blauwe knopen een grootste onafhankelijke verzameling. In de grafentheorie verstaat men onder onafhankelijke verzameling of stabiele verzameling (independent set in het Engels) van een graaf, een deelverzameling van de knopen van die graaf die twee aan twee niet verbonden zijn door een zijde.
Bekijken Clique (grafentheorie) en Onafhankelijke verzameling
Overdekking (topologie)
In de wiskunde is een overdekking van een verzameling X een geindiceerde verzameling C van verzamelingen U_i zodat X een deelverzameling van de vereniging van de verzamelingen U_i is.
Bekijken Clique (grafentheorie) en Overdekking (topologie)
Perfecte graaf
Voorbeeld van een perfecte graaf. In vet is een geïnduceerde subgraaf aangeduid met drie knopen. Het is een clique met chromatisch getal 3. Voor elke subgraaf van deze graaf is het cliquegetal gelijk aan het chromatisch getal. Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf.
Bekijken Clique (grafentheorie) en Perfecte graaf
Polynomiale tijd
In de complexiteitstheorie kan een algoritme in polynomiale tijd uitgevoerd worden als de benodigde tijd, als functie van de grootte van de invoer, begrensd wordt door een polynoom.