Functies en grafieken

Overweeg een eindige set $ X $ van order $ n $ en een symmetrische functie $ f: X \ times X \ rightarrow X $.

$ f $ kan eenvoudig worden beschouwd als een multidigraph met

  • $ n $ "object" -knooppunten, die de elementen van $ X $ vertegenwoordigen, en

  • $ n (n + 1)/2 $ "argument" -knooppunten, die de paren argumenten vertegenwoordigen van $ f $.

Elk van de $ n $ -objectknooppunten heeft $ n + 1 $ outpijlen naar de corresponderende argumentknopen. Elk van de $ n (n + 1)/2 $ -argumentnodes heeft precies 2 inpijlen van de corresponderende objectknooppunten en 1 uit-pijl naar het overeenkomstige "functiewaarde" knooppunt (een objectknooppunt).

Keer nu de situatie om en overweeg een willekeurige multidograaf met $ N = n + n (n + 1)/2 = n (n + 3)/2 $ knooppunten met de eigenschap P , die $ n $ van hen (de object knooppunten) hebben $ n + 1 $ uit-pijlen en een andere $ n (n + 1)/2 $ van hen (de argument knooppunten) hebben precies 2 in-pijlen en 1 uit-pijl.

Vraag : kan - of beter: onder welke voorwaarden kan worden aangetoond dat: a   multidigrafie met eigenschap P is    bipartite , in de betekenis van:

     
      
  • de uitpijlen van een object knooppunt gaan naar een argument knooppunt en vice versa   versa

  •   
  • de in-pijlen van een object knooppunt komen van een argument knooppunt en vice versa   versa.

  •   
2
Je punt is dat je niet-gelabelde digraphs wilt hebben, toch? Dus het objectknooppunt x heeft twee parallelle bogen naar het argumentknooppunt (x, x)? Ik denk dat je n zulke parallelle bogen met verschillende doelen nodig hebt, anders lijkt het me dat tweeslachtigheid niet voldoende is om de grafiek een functionele grafiek te maken. (Een voorbeeld, waarbij de functionele waarden worden vergeten: overweeg n = 3 en de disjuncte unie van een K_ {2,4} en een digraph op drie knooppunten, waarvan één met een outdegree van 4, de andere 2 met elk indegree 2)
toegevoegd de auteur Scott W, de bron

1 antwoord

Het is niet waar, zelfs niet voor $ n = 1 $. Beschouw de grafiek met twee knooppunten, $ a $ en $ b $, met randen als volgt:

  • $ a \ tot a $
  • $ a \ to b $
  • $ b \ tot b $

Dus, $ a $ heeft precies twee uit-pijlen, $ b $ heeft precies twee in-pijlen en precies één -out pijl. Dus het heeft eigenschap $ P $ voor $ n = 1 $ maar is niet tweeledig zoals je wilde, omdat zowel $ a $ als $ b $ zichzelf toewijzen.

(Merk op dat de pijl $ b \ tot b $ zowel bijdroeg aan de in-arrow-som als de out-arrow-som bij $ b $, wat misschien niet de manier is waarop u de dingen wilde beschouwen.)

1
toegevoegd