Reducibilitatea grafurilor și a digrafurilor

Titlul original:

Reducibility of Graphs and Digraphs

Conținutul cărții:

Reducibilitatea grafurilor este unul dintre subiectele importante în problema restrângerii în teoria grafurilor.

De fapt, ștergerea unor vârfuri (muchii) dintr-un graf cu anumite proprietăți poate să nu mențină proprietățile grafului. Atunci când graful își păstrează proprietățile după ștergerea unui vârf (muchie) din setul său de vârfuri (muchii), înseamnă că putem studia graful cu mai puține vârfuri (muchii), ceea ce simplifică studiul nostru pentru acest graf.