10 relaties: Beslissingsprobleem, Clique (grafentheorie), Complementgraaf, Computationele complexiteitstheorie, Deelverzameling, Grafentheorie, NP-moeilijk, NP-volledig, Perfecte graaf, Polynomiale tijd.
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.
Nieuw!!: Onafhankelijke verzameling en Beslissingsprobleem · Bekijk meer »
Clique (grafentheorie)
in rood: een clique van 3 knopen In de grafentheorie is een clique of kliek een deelverzameling van de knopen van een niet-gerichte enkelvoudige graaf, waarvan de geïnduceerde deelgraaf volledig is.
Nieuw!!: Onafhankelijke verzameling en Clique (grafentheorie) · Bekijk meer »
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.
Nieuw!!: Onafhankelijke verzameling en Complementgraaf · Bekijk meer »
Computationele complexiteitstheorie
Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven.
Nieuw!!: Onafhankelijke verzameling en Computationele complexiteitstheorie · Bekijk meer »
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.
Nieuw!!: Onafhankelijke verzameling en Deelverzameling · Bekijk meer »
Grafentheorie
Enkelvoudige graaf met zes knopen De grafentheorie is een deelgebied van de wiskunde dat de eigenschappen van grafen bestudeert.
Nieuw!!: Onafhankelijke verzameling en Grafentheorie · Bekijk meer »
NP-moeilijk
NP-moeilijk is een complexiteitsgraad.
Nieuw!!: Onafhankelijke verzameling en NP-moeilijk · Bekijk meer »
NP-volledig
NP-volledigheid is een concept uit de complexiteitstheorie.
Nieuw!!: Onafhankelijke verzameling en NP-volledig · Bekijk meer »
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.
Nieuw!!: Onafhankelijke verzameling en Perfecte graaf · Bekijk meer »
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.
Nieuw!!: Onafhankelijke verzameling en Polynomiale tijd · Bekijk meer »