La reduction minimale d'un graphe a une reunion de cliques

✍ Scribed by Ioan Tomescu

• Publisher: Elsevier Science
• Year: 1974
• Tongue: English
• Weight: 770 KB
• Volume: 10
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(74)90030-2

✦ Synopsis

Rkwn& On obtient la virleu: mw4mnle de l'indice dc r6ductiol minimate d'un graphe 3 une rCunion de k cliques.

Dam ce qui suit mm uf ilisms la, tern~inalogie de [ 2 1. Un graphe est un graphe compose de deu~ classes de ssmmets qui contiennent re&zctivement p et y sommets, un sbmmet etant reli6 par des a&es a tous ?es sommets qui n'iippartiennent pas 3 une m&ne classe que lui. Nous identit'ions les graphes KP,q et K,,, !qui sont isomorphes comme graphes aux sommets 6tiquetk). Le graphe KO*, est le grsphe compos2 de IZ sommets isok et le graphe K, est le graphe complet % 12 sommets @-clique).

Four WI vraphe G nws d63inissons ies op&ations suivantes sur les .> a&es:

OCR) supg rimer unc aWe entre dew sommets; P, r&or deux sommets par une aMe, e nombre 5, (63 de reduction minimale d II graphe jl une reunion de k cliques comme !e ncambre minimai Sop&a ns (a) et/w (/?j nkxssaire pour transformer le graphe G en k cliwes disjointes sans a&es entre les sommets qui appartiennent aux cliqws differentes (certaines cliques