Les relations d'équivalence couvrent le problème (en théorie des graphes)

Une relation d'équivalence sur un ensemble de sommets finis peut être représentée par un graphique non orienté qui est une union disjointe de cliques. L'ensemble des sommets représente les éléments et une arête indique que deux éléments sont équivalents.

Si j'ai un graphe et des graphes , on dit que est couvert par si l'ensemble des arêtes de est égal à l'union des ensembles d'arêtes de . Les ensembles de de n'ont pas besoin d'être disjoints. Notez que tout graphe non orienté peut être couvert par un nombre fini de relations d'équivalence (c'est-à-dire, union disjointe de graphes cliques). $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G_1,\dots,G_k$ $G$

J'ai plusieurs questions:

Que dire du nombre minimal de relations d'équivalence nécessaires pour couvrir un graphe ? $G$
Comment calculer ce nombre minimal?
Comment calculer une couverture minimale explicite de , c'est-à-dire un ensemble de relations d'équivalence dont la taille est minimale et qui couvrent ? $G$ $G$
Ce problème a-t-il des applications en dehors de la logique de partition (le double de la logique des sous-ensembles )?
Ce problème a-t-il un nom bien établi?

Compte tenu des divers malentendus signalés par les commentaires, voici quelques photos pour illustrer ces concepts. Si vous avez une idée pour une terminologie plus facile à comprendre (au lieu de "couverture", "relation d'équivalence", "union disjointe de cliques" et "pas nécessairement disjointe" union d'ensembles de bords), n'hésitez pas à me le faire savoir.

Voici une image d'un graphique et une relation d'équivalence le couvrant:

Voici une image d'un graphique et deux relations d'équivalence le couvrant:
Il devrait être assez évident qu'au moins deux relations d'équivalence sont nécessaires.

Voici une image d'un graphique et de trois relations d'équivalence le couvrant: graphique et trois relations d'équivalence le couvrant
Il est moins évident qu'au moins trois relations d'équivalence sont requises. Le lemme 1.9 de Dual of the Logic of Subsets peut être utilisé pour montrer que cela est vrai. La généralisation de ce lemme aux opérations nand avec plus de deux entrées a été la motivation de cette question.

algorithms graph-theory clique Thomas Klimpel
la source

Il s'agit d'un problème NP-Complete bien connu . en.wikipedia.org/wiki/Clique_cover_problem

gardenhead

@StephenBly C'est peut-être un problème bien connu, mais le lien wikipedia que vous avez donné ne m'aide pas vraiment. L'article parle d'un problème de couverture de sommet, mais la question ici concerne un problème de couverture de bord. Notez également qu'une relation d'équivalence n'est pas une clique, mais une union disjointe de cliques.

Thomas Klimpel

Que voulez-vous dire par une relation d'équivalence est une union disjointe de cliques? L'ensemble des sommets représente les éléments et une arête indique que deux éléments sont équivalents. Si ce n'est pas la représentation que vous utilisez, vous devez le préciser.

gardenhead

n - 1

$n-1$

n

$n$

n - 1

$n-1$

@YuvalFilmus La question porte sur le plus petit nombre de relations d'équivalence dont l'union est exactement la relation de bord du graphe donné, et non dont l'union inclut simplement le graphe donné.

David Richerby

Réponses:

$\text{eq}(G)$ $\text{cc}(G)$

Il existe des classes de graphiques spéciales où la valeur exacte ou une bonne limite supérieure pour l'un ou l'autre nombre est connue. En général, à ma connaissance, les meilleures limites sont données par Alon [1]:

{Journal}_{2} n - {Journal}_{2} ré \leq eq (g) \leq cc (g) \leq 2 e^{2} (Δ + 1)^{2} \ln n,

$\log_2 n - \log_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$

$\Delta$ $G$ $\lceil n^2/4 \rceil$

$\sf NP$ $\text{eq}(G)$ $\sf NP$

[1] Alon, Noga. "Couvrant les graphiques par le nombre minimum de relations d'équivalence." Combinatorica 6.3 (1986): 201-206.

[2] Blokhuis, Aart et Ton Kloks. "Sur l'équivalence couvrant le nombre de graphiques divisés" Lettres de traitement de l'information 54.5 (1995): 301-304.

[3] Kučera, Luděk, Jaroslav Nešetřil et Aleš Pultr. "Complexité de la dimension trois et certaines caractéristiques de recouvrement des bords des graphiques." Informatique théorique 11.1 (1980): 93-106.

Juho
la source

Le corollaire 1.3 de [1] est exactement ce dont j'avais besoin (dans la version qui s'applique aux compléments d'un chemin). Maintenant, je n'ai plus d'excuse pour ne pas écrire l'article sur l'implication générale "(A, B, C, ...) impliquent (Z, Y, X, ...)" (le séquent du calcul séquentiel) dans la partition logique et logiques non classiques similaires. Mais je suppose que je ne l'écrirai pas avant au moins un autre semestre. Et peut-être que je trouve même une nouvelle excuse en attendant.

Thomas Klimpel

@ThomasKlimpel C'est super! (Pas le fait que vous puissiez trouver une nouvelle excuse, mais que cela a été utile :-))

Juho

Bien que je ne connaisse pas le nom d'un tel problème, je peux montrer que ce problème est NP-difficile.

Pour un graphique sans triangle, toutes les classes d'équivalence doivent correspondre. Le nombre minimum de classes d'équivalence qui couvre le graphique est égal à l'indice chromatique du graphique.

Selon cet article , trouver l'indice chromatique pour un graphique sans triangle est NP-complet.

Chao Xu
la source