Partizionamento di grafi in componenti connesse

Partizionamento di grafi in componenti

connesse

Università Roma Tre – Dipartimento di Matematica e Fisica IN440 – Ottimizzazione Combinatoria

Prof. Marco Liverani

Partizionamento di insiemi e di grafi

§ S ^UBSET -S ^UM e S ^ET -P ^ARTITION sono problemi NP-completi ben noti

§ Tuttavia se si aggiungono vincoli alla modalità con cui costruire i sottoinsiemi, lo spazio delle soluzioni ammissibili si riduce e in determinati casi si arriva a problemi polinomiali

§ I problemi di partizionamento di grafi in componenti connesse sono problemi analoghi, ma con l’aggiunta del vincolo che ciascuna componente della partizione sia un sottografo connesso di G

§ Possono quindi essere essere affrontati e risolti con algoritmi esatti di complessità polinomiale, almeno per alcune classi di grafi

Università Roma Tre – Dipar3mento di Matema3ca e Fisica

Marco Liverani, O;mizzazione Combinatoria 1

Partizionamento di grafi in componenti connesse

§ Dato un grafo G = (V, E) e un intero p > 0, con p ≤ |V|, si chiede di individuare una p-partizione π _p di V in p componenti π _p = {V ₁ , ..., V _p } tali che V ₁ ∪ ... ∪ V _p = V , V _i ∩ V _j per ogni i, j = 1, ..., p con i ≠ j

§ La p-partizione deve essere tale che il sottografo di G indotto da V _k , G[V _k ] , sia connesso per ogni k = 1, ..., p

§ La p-partizione di G è propria se V _k ≠ ∅ per ogni k

§ Indichiamo con ∏ _p (G) l’insieme di tutte le p-partizioni in componenti connesse del grafo G

1

2

8

3

5

4 7

6

1

2

8

3

5

4 7

6 p = 3

V ₁ = {2, 3, 7}

V ₂ = {4, 5, 6, 8}

V ₃ = {1}

π ₃ = {V ₁ , V ₂ , V ₃ }

Partizionamento di grafi in componenti connesse

§ Se il grafo è un albero T (o un cammino, un caso particolare di albero), ottenere una p-partizione del grafo in componenti connesse equivale a rimuovere esattamente p – 1 spigoli da E(T), visto che il cammino tra due vertici qualsiasi di T è unico, basta rimuovere uno spigolo per sconnettere il grafo in due componenti distinte e connesse

§ Le componenti di una p-partizione di un albero sono a loro volta degli alberi

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 3

1

2

8

3

5

4 7

6

1

2

8

3

5

4 7

6

p = 3

si ottiene una 3-partizione dell’albero tagliando 2 spigoli

V ₁ = {2, 3, 7}

V ₂ = {4, 5, 6, 8}

V ₃ = {1}

π ₃ = {V ₁ , V ₂ , V ₃ }

Partizionamento di grafi in componenti connesse

§ Se una p-partizione di un albero può essere ottenuta rimuovendo solo p – 1 spigoli, per un grafo il numero di spigoli da rimuovere per ottenere una p-partizione varia a seconda della topologia del grafo

§ Il problema può essere formulato come un problema di ottimizzazione combinatoria aggiungendo una funzione obiettivo f (π _p ) da ottimizzare:

f : ∏ _p (G) ⟶ ℝ

§ calcolata in base alla partizione del grafo; dato il grafo G = (V, E) e p > 1, si deve trovare la p-partizione π* _p ∈ ∏ _p (G) tale che

§ I problemi si distinguono in due famiglie:

• equipartizione : assegnato un peso a ciascun vertice di un grafo, si cerca la p-partizione che renda equilibrato il peso delle p componenti (si cerca la partizione con la minore differenza di peso tra le componenti)

• clustering : assegnata una distanza o un « indice di dissimilarità » a ciascuna coppia di vertici del grafo, si cerca la p-partizione tale da aumentare la distanza tra i vertici di componenti diverse o ridurre al minimo la distanza tra gli elementi di una stessa componente

§ I problemi di equipartizione e di clustering su grafi generici sono NP-completi

<latexit sha1_base64="ETWA6s+5dq3KSdMhZfOuUh4vtsQ=">AAACLXicbVDLSgMxFM34tr6qLt0Ei9Aq1BkX6kYoutBlBatCpw6Z9I6GZjIhyYhl6Be49g/c+wFu9RNcCOLWL3Bv2rqwrQcCh3PO5d6cUHKmjeu+O2PjE5NT0zOzubn5hcWl/PLKuU5SRaFGE56oy5Bo4ExAzTDD4VIqIHHI4SJsHXX9i1tQmiXizLQlNGJyLVjEKDFWCvLbUdGX7GozkCV8gP2YiSCzQiCxzwT2q5YVj0sd3IvZUJAvuGW3BzxKvF9SqGx9P95DQVaD/JffTGgagzCUE63rnitNIyPKMMqhk/NTDZLQFrmGuqWCxKAbWe9jHbxhlSaOEmWfMLin/p3ISKx1Ow5tMibmRg97XfE/r56aaL+RMSFTA4L2F0UpxybB3ZZwkymghrctIVQxeyumN0QRamyXA1uk5sTAXSdnm/GGexgl5ztlb7fsnXqFyiHqYwatoXVURB7aQxV0gqqohih6QM/oBb06T86b8+F89qNjzu/MKhqA8/UDcFCqhg==</latexit>

f (p ^⇤ _p ) = min _{p p 2P p (G)} f (p _p )

§ Si vuole distribuire equamente il peso dei vertici fra tutte le p componenti del grafo G

30 65

20 65 70

70

28

50 35

50 45 18

Problemi di equipartizione

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 5

1

2 3

5

4 7

6 10 10

15

3 50

5 20

1

2 3

5

4 7

6 10 10

15

3 50

5 20

1

2 3

5

4 7

6 10 10

15

3 50

5 20

1 2 3 4 5 6 7

10 10

15 40 5 60 20

p = 3

p = 3

1 2 3 4 5 6 7

10 10

15 40 5 60 20

§ Vogliamo aggregare nella stessa componente elementi simili, meno distanti, minimizzando la dissimilarità all’interno delle componenti o massimizzando la distanza tra componenti

§ La scelta della partizione ottima dipende dalla funzione obiettivo con cui scegliamo di misurare la distanza tra le componenti o la similarità interna ad una componente

30 Problemi di clustering

1

2 3

5

4 7

6

10 10

15

50

5 5

20

5 20

5 30 20

5

5

1

2 3

5

4 7

6

10 10

15

50

5 5

20

5 20

5 30

p = 3 20

Problemi di equipartizione

§ Assegnato un peso w _i = w(v _i ) > 0 a ciascun vertice v _i ∈ V (G) di un grafo, si cerca la p-partizione π _p che renda equilibrato il peso delle p componenti di π _p

§ Si può definire il peso di una componente di π _p = {V ₁ ,...,V _p } :

§

e il peso medio di una componente della partizione π _p :

§ È chiaro che l’obiettivo ottimo di un’equipartizione è quello di ottenere una p-partizione π _p tale che W(V _k ) = μ per ogni k = 1, ..., p

§ Non sempre però, tenendo conto della natura discreta del problema, è possibile costruire una p -partizione con W _k = μ per ogni k = 1, ..., p (ad esempio, μ potrebbe essere non intero)

§ Vengono così definiti problemi diversi con differenti funzioni obiettivo, tutte finalizzate a produrre un’equipartizione del grafo

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 7

<latexit sha1_base64="3W3+vfJ+hAqtM0/fJZ6AxjGaryU=">AAACInicbZC7TgJBFIZnvSLeUEubiWgChWTXQm1MiDaWmMglAbKZHQ4wYXZ2MzOLkg0v4BvQ+wBa6iPYGSoTe1/D4VII+CeTfPnPOTlnfi/kTGnb/rKWlldW19YTG8nNre2d3dTefkkFkaRQpAEPZMUjCjgTUNRMc6iEEojvcSh7nZtRvdwFqVgg7nUvhLpPWoI1GSXaWG7quOx28BUuZ0puJ2ugpiLfjbu4xgQ2Vh8/ZLpZN5W2c/ZYeBGcKaTzp4NXB4aDgpv6qTUCGvkgNOVEqapjh7oeE6kZ5dBP1iIFIaEd0oKqQUF8UPV4/Js+PjFOAzcDaZ7QeOz+nYiJr1TP90ynT3RbzddG5n+1aqSbl/WYiTDSIOhkUTPiWAd4FA1uMAlU854BQiUzt2LaJpJQbQKc2RIqTjQ89pMmGWc+h0UoneWc85xz56Tz12iiBDpERyiDHHSB8ugWFVARUfSEXtAbereerQ/r0xpOWpes6cwBmpH1/Qu9ZqYX</latexit>

W _k = W (V _k ) = Â _{v2V k} w(v)

<latexit sha1_base64="Stqn36CZJtZXahTYd4YOrQQVVPU=">AAACIXicbVC7TsMwFL0p7/IqMLJYVEgwUCUMwIJAMMAIEgWkJlSO67RWbSeyHaCK8gF8Bx/ACp/ABmyIgZHfwG0ZoOVIlo7OOVf3+oQJZ9q47rtTGBkdG5+YnCpOz8zOzZcWFs91nCpCqyTmsboMsaacSVo1zHB6mSiKRcjpRdg+7PoX11RpFssz00loIHBTsogRbKxUL5V9kaJd5EcKk8zXqahnbNfLryS6Wbuus/U8S3KbcituD2iYeD+kvL/3+Xq7sXN0Ui99+Y2YpIJKQzjWuua5iQkyrAwjnOZFP9U0waSNm7RmqcSC6iDrfSZHq1ZpoChW9kmDeurviQwLrTsitEmBTUsPel3xP6+WmmgnyJhMUkMl6S+KUo5MjLrNoAZTlBjesQQTxeytiLSw7cXY/v5sSTTHht7mRduMN9jDMDnfrHhbFe/UVnQAfUzCMqzAGniwDftwDCdQBQJ38ACP8OTcO8/Oi/PWjxacn5kl+APn4xuiHac4</latexit>

µ = Â ^{n i=1} w(v _i )

p

Problemi di equipartizione

§ Per ciascuna p-parLzione π _p = {V ₁ , ..., V _p } di G possiamo definire il veNore W = (W ₁ , ..., W _p ) ∈ ℤ ^p , con W _k = W(V _k )

§ In un problema di equiparLzione si vuole oNenere una p-parLzione in cui il veNore W si avvicini il più possibile al veNore μ = (μ, ..., μ)

§ Per sLmare la distanza fra W e μ possiamo uLlizzare il conceNo di norma di un veNore: ∥W − μ∥

§ Vengono così definite diverse funzioni obiePvo per il problema della equiparLzione in p componenL connesse di un grafo G:

• Norma L ₁ :

• Norma L ₂ :

• Norma L _∞ :

§ Il problema di oPmizzazione chiede di trovare una tale che

<latexit sha1_base64="vJLMvWjI4k4/aQK4vxVu7823sNE=">AAACRnicbVDLThsxFL0TWqChpaFddmM1QgqLRuMuWjZIEd2wpBJJkDJh5HE8wYo9Y/mBiCbzKf2FfgcfgERZ0C07dohtPQmVeB3J0rnnnqvrexIluLFheBnUll69Xl5ZfVNfe/tu/X1j40PP5E5T1qW5yPVhQgwTPGNdy61gh0ozIhPB+snkR9XvnzBteJ4d2KliQ0nGGU85JdZLcWMvbUWKx2oL7aBoFklij5O06JfoC/pfRNKV0SzGlcM4GReTHVweKTTrt3rxZGvudLO40Qzb4RzoOcH3pNnZvP1z8as+3o8b19Eop06yzFJBjBngUNlhQbTlVLCyHjnDFKETMmYDTzMimRkW84tLtOmVEUpz7V9m0Vx9OFEQacxUJt5ZXWGe9irxpd7A2XR7WPBMOcsyuliUOoFsjqr40IhrRq2YekKo5v6viB4TTaj1IT/aoowglp2WdZ8MfprDc9L72sbf2vgnbnZ2YYFV+ASfoQUYvkMH9mAfukDhN5zDFfwNzoKb4Da4W1hrwf3MR3iEGvwDtCu0SQ==</latexit>

f (p _p ) = kW µk 1 = Â _k=1 ^p |W (V k ) µ|

<latexit sha1_base64="4l963pn7r4/Amwy1ZJTRoBKtbk4=">AAACSHicbVDLSiNBFK2OOmrGGaMu3RQGIVlM6M5C3QhBN4MrBfOAdGyqK9WxSFV3UQ8xtP0p/oPfMR/gY6U7t25E3FmdRPAxBwrOPfdcbt0TCkaVdt07pzAzO/djfmGx+HPp1+/l0spqSyVGYtLECUtkJ0SKMBqTpqaakY6QBPGQkXY43M/77TMiFU3iYz0SpMfRIKYRxUhbKSgdRBVf0EBU4S70L3yO9GkYpe0M/oHvhc9N5l8E9dyhDA/S4a6XnQhYaVdawbA6dprqST0old2aOwb8TrwpKTc2n29vLouDw6D06PcTbDiJNWZIqa7nCt1LkdQUM5IVfaOIQHiIBqRraYw4Ub10fHMGN63Sh1Ei7Ys1HKsfJ1LElRrx0DrzO9TXXi7+r9c1OtrppTQWRpMYTxZFhkGdwDxA2KeSYM1GliAsqf0rxKdIIqxtzJ+2CMWQJudZ0Sbjfc3hO2nVa95WzTvyyo09MMECWAcboAI8sA0a4C84BE2AwRW4BvfgwfnnPDkvzuvEWnCmM2vgEwqFNwjItEc=</latexit>

f (p _p ) = kW µk 2 = Â _k=1 ^p (W (V _k ) µ) ²

<latexit sha1_base64="j+P7uSZtK0KXGGqAdpitF1gVsYk=">AAACU3icbVA9TyMxFHQWjuPCVw5KGouAFCQu2r3i7hqkCBpKkEiClI1WXscLVmyvZb9FRJv9WzSU/AYKSiokqI+GBm/CScfHkyyNZ+b5+U2sBbfg+7cVb2b2y9zX+W/VhcWl5ZXa99WOTTNDWZumIjUnMbFMcMXawEGwE20YkbFg3Xi4X+rdc2YsT9UxjDTrS3KqeMIpAUdFtXbSCDWP9DbexeE4lATO4iTvFvgH/ncJZVaE4yjkKoFRaZPkIsqHu8EODgcp2B2sCzzuNjrRcHvSlo2jWt1v+pPCH0HwCuqtzb+X1+cLT4dR7d49RTPJFFBBrO0FvoZ+TgxwKlhRDTPLNKFDcsp6Dioime3nk/ULvOWYAU5S444CPGH/78iJtHYkY+csV7LvtZL8TOtlkPzp51zpDJii00FJJjCkuMwSD7hhFMTIAUINd3/F9IwYQsEl/maKtoIAuyiqLpngfQ4fQednM/jVDI6CemsPTWseraMN1EAB+o1a6AAdojai6ArdoQf0WLmpPHueNzu1epXXnjX0prylF2QVt5U=</latexit>

f (p _p ) = kW µk • = max _k=1,...,p |W (V k ) µ|

<latexit sha1_base64="o4lhn9c1UygPGunNBaetsizhW24=">AAACLXicbVDLSgMxFM3Ud31VBTdugkWoLuqMC3Uj+FjosgVrC51xyKQZDWYyIcmIZZjP8Dv8AKEr/QQFQdy48DdMHwvbeiBwOOdc7s0JBKNK2/aHlZuYnJqemZ3Lzy8sLi0XVlavVJxITGo4ZrFsBEgRRjmpaaoZaQhJUBQwUg/uzrp+/Z5IRWN+qduCeBG64TSkGGkj+YXdsOQKer3ji214BN2Icj81gi+gSzl0K4aVzrcz2IuZkF8o2mW7BzhOnAEpHp98v3c669WKX/hxWzFOIsI1ZkippmML7aVIaooZyfJuoohA+A7dkKahHEVEeWnvYxncMkoLhrE0j2vYU/9OpChSqh0FJhkhfatGva74n9dMdHjopZSLRBOO+4vChEEdw25LsEUlwZq1DUFYUnMrxLdIIqxNl0NbhGJIk4csb5pxRnsYJ1d7ZWe/7FRNRaegj1mwATZBCTjgAByDC1ABNYDBI3gGL+DVerLerE/rqx/NWYOZNTAE6+cXRlurGw==</latexit>

f (p ^⇤ _p ) = min

p _p 2P p (G) f (p _p )

<latexit sha1_base64="jB7urD2CHf5/oSLra4v4UwmG8V0=">AAACEnicbVC7SgNBFJ2N7/haH53NYBB8QNi1UEvRQssIJhGy6zI7uYlDZmeHmVkxhnyBrR9gYaOfYCe2/oBf4BfYO0ksNPHAhcM593IuJ5acaeN5H05ubHxicmp6Jj87N7+w6C4tV3SaKQplmvJUXcREA2cCyoYZDhdSAUliDtW4ddzzq9egNEvFuWlLCBPSFKzBKDFWitzVQLLL7UjigAkclFgkN0+2IrfgFb0+8Cjxf0jhcOfr8Q4KshS5n0E9pVkCwlBOtK75njRhhyjDKIduPsg0SEJbpAk1SwVJQIed/vddvGGVOm6kyo4wuK/+vuiQROt2EtvNhJgrPez1xP+8WmYaB2GHCZkZEHQQ1Mg4NinuVYHrTAE1vG0JoYrZXzG9IopQYwv7kyI1JwZuunnbjD/cwyip7Bb9vaJ/Zis6QgNMozW0jjaRj/bRITpFJVRGFN2iB/SEnp1758V5dd4Gqznn52YF/YHz/g3pgaBt</latexit>

p ^⇤ _p 2 P p (G)

W 2 = 35 W ₃ = 50 W ₂ = 25 W ₁ = 39

Problemi di equipartizione

Università Roma Tre – Dipar=mento di Matema=ca e Fisica

Marco Liverani, O>mizzazione Combinatoria 9

1

2 3

5

4 7

6 10 10

15

4 50

5 20

p = 3 ⟹ µ = 114/3 = 38

1

2 3

5

4 7

6 10 10

15

4 50

5 20

<latexit sha1_base64="m4B/B+TK5iE4fSHlaztU8ejRECA=">AAACMnicbVDLSgMxFM3UV62vqks3oUWoiGWmShVBKLpx4aKCfUCnDJk004ZmHiQZsUznL1z5HX6AW/2DuhMXbvwI04dgWw8Ezj3nXu7NsQNGhdT1gZZYWFxaXkmuptbWNza30ts7VeGHHJMK9pnP6zYShFGPVCSVjNQDTpBrM1Kzu1dDv3ZPuKC+dyd7AWm6qO1Rh2IklWSlT24s4xw6OTOg1vEBvIBm33SR7NhOVIvhEfwtTDeMzb5lqI5C0Upn9bw+ApwnxoRkSxnz8HFQ6pWt9JfZ8nHoEk9ihoRoGHogmxHikmJG4pQZChIg3EVt0lDUQy4RzWj0uxjuK6UFHZ+r50k4Uv9ORMgVoufaqnN4rJj1huJ/XiOUzlkzol4QSuLh8SInZFD6cBgVbFFOsGQ9RRDmVN0KcQdxhKUKdGpLIBiS5CFOqWSM2RzmSbWQN4p541ZFdAnGSII9kAE5YIBTUALXoAwqAIMn8AJewZv2rL1rH9rnuDWhTWZ2wRS07x/wDKue</latexit>

L ₁ : f (p ₃ ) = kW µk 1 = 26

<latexit sha1_base64="TPf4vdZtbmxf5eCrWcC/eCN7u1w=">AAACPHicbVDLSsQwFE19O75GXboJiqCIQ6ugIiiDbly4UHAcYTKUNJNqME1LciuW2r/wE/wOP8CtbtwLLsStazMPwdeBwLnn3sO9OUEihQHXfXb6+gcGh4ZHRktj4xOTU+XpmVMTp5rxGotlrM8CargUitdAgORnieY0CiSvB5f77X79imsjYnUCWcKbET1XIhSMgpX88u6hT4QKIdvG4RJJhL++jHcwuSERhYsgzOsFXsVfBYnSgtz0DHbMW/fLC27F7QD/JV6PLFTnycrtczU78suvpBWzNOIKmKTGNDw3gWZONQgmeVEiqeEJZZf0nDcsVTTippl3/lngRau0cBhr+xTgjvrdkdPImCwK7GT7YvO71xb/6zVSCLeauVBJClyx7qIwlRhi3A4Nt4TmDGRmCWVa2Fsxu6CaMrDR/tiSGEmBXxclm4z3O4e/5HSt4m1UvGMb0R7qYgTNoXm0hDy0iaroAB2hGmLoDj2gR/Tk3Dsvzpvz3h3tc3qeWfQDzscnvQWwqA==</latexit>

L _• : f (p ₃ ) = kW µk • = 13

<latexit sha1_base64="aSGEwbkWL0C3LMBtkwHaIsaGrjg=">AAACM3icbVDLSgMxFM34rPVVdekmtAgVscy0vhCEohsXLirYB3TKkEkzbWjmQZIRy3T+wp3f4Qe41S8o7kRw5T+YPgTbeiBw7jn3cm+OHTAqpK73tbn5hcWl5cRKcnVtfWMztbVdEX7IMSljn/m8ZiNBGPVIWVLJSC3gBLk2I1W7czXwq/eEC+p7d7IbkIaLWh51KEZSSVbq+MbKn0MnawbUKuzDC2j2TBfJtu1E1Rgewt/CdMPY7Fl51VEwjqxURs/pQ8BZYoxJppg2Dx77xW7JSn2ZTR+HLvEkZkiIuqEHshEhLilmJE6aoSABwh3UInVFPeQS0YiG34vhnlKa0PG5ep6EQ/XvRIRcIbqurToH14ppbyD+59VD6Zw1IuoFoSQeHi1yQgalDwdZwSblBEvWVQRhTtWtELcRR1iqRCe2BIIhSR7ipErGmM5hllTyOeMkZ9yqiC7BCAmwC9IgCwxwCorgGpRAGWDwBF7AK3jTnrV37UP7HLXOaeOZHTAB7fsHdpSr2g==</latexit>

L ₂ : f (p ₃ ) = kW µk 2 = 314

W ₃ = 50 W 1 = 29

1

2 3

5

4 7

6 10 10

15

4 50

5 20

<latexit sha1_base64="h18UZO0tTaBoOUZ+CUXnxP3XH6g=">AAACM3icbVDLSgMxFM34rPVVdekmtAgVscy0vhCEohsXLirYB3TKkEkzbWjmQZIRy3T+wp3f4Qe41S8o7kRw5T+YPgTbeiBw7jn3cm+OHTAqpK73tbn5hcWl5cRKcnVtfWMztbVdEX7IMSljn/m8ZiNBGPVIWVLJSC3gBLk2I1W7czXwq/eEC+p7d7IbkIaLWh51KEZSSVbq+MbKn0MnawbUKuzDC2j2TBfJtu1E1Rgewt/CdMPY7Fl51ZEvHFmpjJ7Th4CzxBiTTDFtHjz2i92Slfoymz4OXeJJzJAQdUMPZCNCXFLMSJw0Q0EChDuoReqKesglohENvxfDPaU0oeNz9TwJh+rfiQi5QnRdW3UOrhXT3kD8z6uH0jlrRNQLQkk8PFrkhAxKHw6ygk3KCZasqwjCnKpbIW4jjrBUiU5sCQRDkjzESZWMMZ3DLKnkc8ZJzrhVEV2CERJgF6RBFhjgFBTBNSiBMsDgCbyAV/CmPWvv2of2OWqd08YzO2AC2vcPeC2r2w==</latexit>

L ₂ : f (p ₃ ) = kW µk 2 = 234

<latexit sha1_base64="bGQr7xTQIghZuxEKmqXwtye0ujo=">AAACMnicbVDLSgMxFM3UV62vqks3oUWoiGWmFhVBKLpx4aKCfUCnDJk004ZmHiQZsUznL1z5HX6AW/2DuhMXbvwI04dgWw8Ezj3nXu7NsQNGhdT1gZZYWFxaXkmuptbWNza30ts7VeGHHJMK9pnP6zYShFGPVCSVjNQDTpBrM1Kzu1dDv3ZPuKC+dyd7AWm6qO1Rh2IklWSlizeWcQ6dnBlQ6/gAXkCzb7pIdmwnqsXwCP4WphvGZt8yVEehaKWzel4fAc4TY0KypYx5+Dgo9cpW+sts+Th0iScxQ0I0DD2QzQhxSTEjccoMBQkQ7qI2aSjqIZeIZjT6XQz3ldKCjs/V8yQcqX8nIuQK0XNt1Tk8Vsx6Q/E/rxFK56wZUS8IJfHweJETMih9OIwKtignWLKeIghzqm6FuIM4wlIFOrUlEAxJ8hCnVDLGbA7zpFrIGyd541ZFdAnGSII9kAE5YIBTUALXoAwqAIMn8AJewZv2rL1rH9rnuDWhTWZ2wRS07x/s2quc</latexit>

L ₁ : f (p ₃ ) = kW µk 1 = 24

<latexit sha1_base64="yQ1hGwgCVcxFq+1efOj4MCiMuB4=">AAACPHicbVDLSsQwFE19O75GXboJiqCIQ6ugIiiDbly4UHAcYTKUNJNqME1LciuW2r/wE/wOP8CtbtwLLsStazMPwdeBwLnn3sO9OUEihQHXfXb6+gcGh4ZHRktj4xOTU+XpmVMTp5rxGotlrM8CargUitdAgORnieY0CiSvB5f77X79imsjYnUCWcKbET1XIhSMgpX88u6hT4QKIdvG4RJJhL++jHcwuSERhYsgzOsFXsVfBYnSgtz0DHbMW/PLC27F7QD/JV6PLFTnycrtczU78suvpBWzNOIKmKTGNDw3gWZONQgmeVEiqeEJZZf0nDcsVTTippl3/lngRau0cBhr+xTgjvrdkdPImCwK7GT7YvO71xb/6zVSCLeauVBJClyx7qIwlRhi3A4Nt4TmDGRmCWVa2Fsxu6CaMrDR/tiSGEmBXxclm4z3O4e/5HSt4m1UvGMb0R7qYgTNoXm0hDy0iaroAB2hGmLoDj2gR/Tk3Dsvzpvz3h3tc3qeWfQDzscnu2ywpw==</latexit>

L _• : f (p ₃ ) = kW µk • = 12

Problemi di equipartizione

§ Altre funzioni obiePvo per problemi di equiparLzione:

• Max-Min : si vuole massimizzare il minimo

• Min-Max : si vuole minimizzare il massimo

• MUP (most uniform par22on):

si vuole minimizzare la massima differenza

<latexit sha1_base64="swkWbS55iF6KpbULd3IwjblCd28=">AAACaXicbZFdixMxFIYz49daP7arIKI3B4vQylJmvFARhFUv9LIrtl3o1CGTZtowSSYkZ3TLMH9t/4M3gtdeeOEP8NZ0uoK764HAw/vm5BzeZEYKh1H0PQgvXb5y9drO9c6Nm7du73b37kxcWVnGx6yUpT3KqONSaD5GgZIfGcupyiSfZsXbjT/9zK0Tpf6Ia8Pnii61yAWj6KW0W+T9xIjUDOAVJErotC48xfuQLEp0+2AamPYnaTGA5INYrpBaW34B3/LpSWpeQtu9Qe8repzW7WOQCA3JyFP/3aCBvyPSbi8aRm3BRYhPoXfw+se3k5N7h6O0+9NvwSrFNTJJnZvFkcF5TS0KJnnTSSrHDWUFXfKZR00Vd/O6DaWBx15ZQF5afzRCq/7bUVPl3Fpl/qaiuHLnvY34P29WYf5iXgttKuSabQfllQQsYZMwLITlDOXaA2VW+F2BrailDP0/nJlinKTIj5uOTyY+n8NFmDwdxs+G8aGP6A3Z1g55SB6RPonJc3JA3pMRGRNGvpLfAQmC4Fe4F94PH2yvhsFpz11ypsLeH33buxc=</latexit>

f (p _p ) = min

k=1,...,p W (V _k ) ) p ^⇤ p : f (p ^⇤ _p ) max

p _p 2P p (G) f (p _p )

<latexit sha1_base64="jzsCpiv/xd1o/DzrpOq3+2h5msI=">AAACaXicbZFdixMxFIYz49daP7arIKI3B4vQylJmvFARhFUv9LIrtl3o1CGTZtowSSYkZ3TLMH9t/4M3gtdeeOEP8NZ0uoK764HAw/vm5BzeZEYKh1H0PQgvXb5y9drO9c6Nm7du73b37kxcWVnGx6yUpT3KqONSaD5GgZIfGcupyiSfZsXbjT/9zK0Tpf6Ia8Pnii61yAWj6KW0W+T9xIjUDOAVJIoep3XhKd6HZFGi2wfTwLQ/SYsBJB/EcoXU2vIL+JZPT1LzEtruDXpfCZ3W7WOQCA3JyFP/3aCBvyPSbi8aRm3BRYhPoXfw+se3k5N7h6O0+9NvwSrFNTJJnZvFkcF5TS0KJnnTSSrHDWUFXfKZR00Vd/O6DaWBx15ZQF5afzRCq/7bUVPl3Fpl/qaiuHLnvY34P29WYf5iXgttKuSabQfllQQsYZMwLITlDOXaA2VW+F2BrailDP0/nJlinKTIj5uOTyY+n8NFmDwdxs+G8aGP6A3Z1g55SB6RPonJc3JA3pMRGRNGvpLfAQmC4Fe4F94PH2yvhsFpz11ypsLeH35Xuxc=</latexit>

f (p _p ) = max

k=1,...,p W (V _k ) ) p ^⇤ p : f (p ^⇤ _p ) min

p _p 2P p (G) f (p _p )

<latexit sha1_base64="HpbzmDknMFnfDp5V+WLTtOXkFgY=">AAACiXicbZFbi9NAFMcn8bZ2vVQFffDl6CI0slsSH3RZEFb3QR+7YtuFpobJdNIMnUyGmRPdEvIJ/E77MQSfffDZb+A0reBeDgz8+P/nXDgn1VJYDMOfnn/t+o2bt7Zud7bv3L13v/vg4ciWlWF8yEpZmpOUWi6F4kMUKPmJNpwWqeTjdHG08sdfubGiVJ9xqfm0oHMlMsEoOinpfs96sRaJDuAtxAU9TeqFo2gX4lmJdhd0A+PeKFkEsOd8oZI6v8rPA4g/iXmO1JjyG7iSX14m+gDa6isMNtltM4iFgnjgqPchaODfCEl3J+yHbcBliDawc/ju14+zs8fHg6T7203BqoIrZJJaO4lCjdOaGhRM8qYTV5ZryhZ0zicOFS24ndbt0hp44ZQZZKVxTyG06v8ZNS2sXRap+1lQzO1FbyVe5U0qzPantVC6Qq7YulFWScASVheAmTCcoVw6oMwINyuwnBrK0N3pXBdtJUV+2nTcZqKLe7gMo1f96HU/OnYrek/WsUWekuekRyLyhhySj2RAhoSRP94TD7xn/rYf+fv+wfqr721yHpFz4R/9BayDw9Y=</latexit>

f (p _p ) = max

k=1,...,p W (V _k ) min

h=1,...,p W (V _h ) ) p ^⇤ p : f (p ^⇤ _p ) min

p _p 2P p (G) f (p _p )

Problemi di clustering

§ Assegnata una distanza o un indice di dissimilarità d _{i, j} ≥ 0 a ciascuna coppia di vertici v _i , v _j ∈ V(G) del grafo, si cerca la p-partizione π _p di G tale da aumentare la distanza tra i vertici di componenti diverse o ridurre al minimo la distanza tra gli elementi della stessa componente

§ La distanza o indice di dissimilarità tra le coppie di vertici del grafo può essere assegnata tramite una matrice quadrata di ordine n, D = (d _{i, j} ) , tale che:

d _{i, j} ≥ 0 per ogni i, j = 1, ..., n d _{i, j} = d _{j, i} per ogni i, j = 1, ..., n

d _i,i = 0 per ogni i = 1, ..., n

§ Anche in questo caso possiamo definire numerosi problemi di ottimizzazione combinatoria al variare della funzione obiettivo da minimizzare o da massimizzare; in particolare le funzioni obiettivo sono di due tipi:

• funzioni per la creazione di partizioni in cui sia massima l’omogeneità all’interno delle componenti (inner dissimilarity): le componenti conterranno elementi poco “distanti/dissimili” fra di loro

• funzioni per la creazione di partizioni in cui sia massima la separazione fra le componenti : le componenti sono costruite in modo da aumentare la distanza minima tra gli elementi di componenti diverse

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 11

Problemi di clustering

Alcune funzioni obie-vo per problemi di clustering:

§ Massimo diametro

• Consente di massimizzare l’omogeneità all’interno delle componen4 della par4zione, chiedendo di produrre componen4 in cui sia minimo il massimo diametro delle componen4 stesse

• Data una p-par4zione π _p ∈ Π _p (G) del grafo G, π _p = {V ₁ ,...,V _k }, definiamo il diametro di una componente ponendo d(V _k ) = max{d _{i, j} : v _i , v _j ∈ V _k }

• In questo caso cerchiamo π ^* _p tale che

§ Somma delle distanze

• Consente di massimizzare l’omogeneità all’interno delle componen4, producendo la par4zione per cui sia minima la somma delle distanze tra gli elemen4 della stessa componente

• Anche in questo caso si cerca π ^* p tale che

<latexit sha1_base64="nBqDA3HSNHXu4e8SXjxfjnX5SjY=">AAACUXicbVBNbxMxFHSWr5ICTeHI5YkKqUhRtMuBcqnUwoVjESStlI0sr/M2ceP1WvbbqNFqfxWnXvonOHFAHIGfwA3n40BbRrI0mnlP8zyZ1cpTHH9rRXfu3rv/YOthe/vR4yc7nd2nA19WTmJflrp0Z5nwqJXBPinSeGYdiiLTeJrN3i/90zk6r0rzmRYWR4WYGJUrKShIvPMp30+t4vYVHEJaiAtezwJLupCOS/JdsA2kGnNK640956oLc34OqTIw4LMGxrwO0nkYdGoypbThnb24F68At0myIXtHx/GX77tX5oR3foY0WRVoSGrh/TCJLY1q4UhJjU07rTxaIWdigsNAjSjQj+rV5xt4GZQx5KULzxCs1H83alF4vyiyMFkImvqb3lL8nzesKH87qpWxFaGR66C80kAlLJuEsXIoSS8CEdKpcCvIqXBCUuj7Wor1WhBeNO3QTHKzh9tk8LqXvOklH0NF79gaW+w5e8H2WcIO2BH7wE5Yn0l2yX6wX+x362vrT8SiaD0atTY7z9g1RNt/AcX1tao=</latexit>

f (p _p ) = max

k=1,...,p

⇢

v _i max ,v _j 2V k d _{i, j}

<latexit sha1_base64="QcGnBRp6FqXZ9h+4XQF7+td79Es=">AAACR3icbZA9axtBEIb3FCe2lQ/LcelmsQnIEMSdC9uNsUkahzQORLJBJy97qzlprb29ZXdORBxX5+f4N7hMHVKkScqU6UIIBLL6KOKPFxZenplhZt/EKOkwDL8GtQdLDx8tr6zWHz95+mytsf684/LCCmiLXOX2POEOlNTQRokKzo0FniUKzpLR62n9bAzWyVy/x4mBXsYHWqZScPSINd6kzdhIZnboIY1dkbFy5F1UXRgaK0ixuaBjJl/SMbuksdS0w0YV7bPSo8uKxlYOhrjDGtthK5yJ3jXRwmwfv/378ejP9edT1vgR93NRZKBRKO5cNwoN9kpuUQoFVT0uHBguRnwAXW81z8D1ytmXK/rCkz5Nc+ufRjqj/0+UPHNukiW+M+M4dLdrU3hfrVtgetArpTYFghbzRWmhKOZ0mh/tSwsC1cQbLqz0t1Ix5JYL9Cnf2GKc4ggfqrpPJrqdw13T2W1Fe63onY/oFZlrhWySLdIkEdknx+SEnJI2EeSKfCHfyPfgU/Az+BX8nrfWgsXMBrmhWvAP3Nm1EQ==</latexit>

f (p _p ) =

 p

k=1 Â

v _i ,v _j 2V k

d _{i, j}

!

<latexit sha1_base64="o4lhn9c1UygPGunNBaetsizhW24=">AAACLXicbVDLSgMxFM3Ud31VBTdugkWoLuqMC3Uj+FjosgVrC51xyKQZDWYyIcmIZZjP8Dv8AKEr/QQFQdy48DdMHwvbeiBwOOdc7s0JBKNK2/aHlZuYnJqemZ3Lzy8sLi0XVlavVJxITGo4ZrFsBEgRRjmpaaoZaQhJUBQwUg/uzrp+/Z5IRWN+qduCeBG64TSkGGkj+YXdsOQKer3ji214BN2Icj81gi+gSzl0K4aVzrcz2IuZkF8o2mW7BzhOnAEpHp98v3c669WKX/hxWzFOIsI1ZkippmML7aVIaooZyfJuoohA+A7dkKahHEVEeWnvYxncMkoLhrE0j2vYU/9OpChSqh0FJhkhfatGva74n9dMdHjopZSLRBOO+4vChEEdw25LsEUlwZq1DUFYUnMrxLdIIqxNl0NbhGJIk4csb5pxRnsYJ1d7ZWe/7FRNRaegj1mwATZBCTjgAByDC1ABNYDBI3gGL+DVerLerE/rqx/NWYOZNTAE6+cXRlurGw==</latexit>

f (p ^⇤ _p ) = min

p _p 2P ^p (G) f (p _p )

<latexit sha1_base64="o4lhn9c1UygPGunNBaetsizhW24=">AAACLXicbVDLSgMxFM3Ud31VBTdugkWoLuqMC3Uj+FjosgVrC51xyKQZDWYyIcmIZZjP8Dv8AKEr/QQFQdy48DdMHwvbeiBwOOdc7s0JBKNK2/aHlZuYnJqemZ3Lzy8sLi0XVlavVJxITGo4ZrFsBEgRRjmpaaoZaQhJUBQwUg/uzrp+/Z5IRWN+qduCeBG64TSkGGkj+YXdsOQKer3ji214BN2Icj81gi+gSzl0K4aVzrcz2IuZkF8o2mW7BzhOnAEpHp98v3c669WKX/hxWzFOIsI1ZkippmML7aVIaooZyfJuoohA+A7dkKahHEVEeWnvYxncMkoLhrE0j2vYU/9OpChSqh0FJhkhfatGva74n9dMdHjopZSLRBOO+4vChEEdw25LsEUlwZq1DUFYUnMrxLdIIqxNl0NbhGJIk4csb5pxRnsYJ1d7ZWe/7FRNRaegj1mwATZBCTjgAByDC1ABNYDBI3gGL+DVerLerE/rqx/NWYOZNTAE6+cXRlurGw==</latexit>

f (p ^⇤ _p ) = min

p (G) f (p _p )

V 2

V 1

V ₂ V ₁

Problemi di clustering

§ Ad esempio, consideriamo il seguente grafo G e cerchiamo una parLzione in p = 2 componenL connesse in modo da oPmizzare le due funzioni obiePvo «Massimo diametro» e «Somma delle distanze»

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 13

1 2

3 20 4

10

30

40 30 20

1 2

3 20 4

10

30

40 30 20

1 2

3 4

10 20

30

40 30 20

Somma delle distanze:

π ^* _p = {{1, 2}, {3, 4}}

f (π ^* _p ) = 40

Massimo diametro:

π ^* _p = {{1, 2, 3}, {4}}

f (π ^* _p ) = 20

Problemi di clustering

§ Minimo split

• Lo split di una componente V _k della p-partizione è la minima distanza o dissimilarità di un elemento di V _k con elementi esterni a V k :

• La funzione obiettivo minimo split chiede di massimizzare la distanza tra le componenti, massimizzando il minimo valore dello split fra tutte le componenti della partizione

• La partizione ottima è π ^* _p tale che

§ Somma delle distanze tra cluster

• Chiede di massimizzare la distanza tra le componenti massimizzando la somma delle distanze tra gli elementi di una componente e tutti gli elementi adiacenti, esterni alla componente stessa

<latexit sha1_base64="I9O6OIdbmDfAj82XOr2t35RmMdQ=">AAACRnicbVC7ThwxFL2zCYQsj2ySMo0VhAQSWs1QEJpIJDSURMouSDsry+P1gBk/RvadFavRfEmq/EB6/oAPoEmRpKSji9LGu0sRIEeydHzOvTr2yUolPcbx96j15OnC4rOl5+3lldW1F52Xr/reVo6LHrfKupOMeaGkET2UqMRJ6QTTmRLHWXEw9Y/HwnlpzWeclGKo2amRueQMg0Q7h6nO7EWdorhAn9c+ZGLTbPZpsUXek1RLQ+sxlSSVhvSLbTKm5yQ1Fmd3WjRkRGu5Tc4b2lmPu/EM5DFJ7sj6/of466/LvS9HtHOTjiyvtDDIFfN+kMQlDmvmUHIlmnZaeVEyXrBTMQjUMC38sJ79uCEbQRmR3LpwDJKZ+u9GzbT3E52FSc3wzD/0puL/vEGF+d6wlqasUBg+D8orRdCSaX1kJJ3gqCaBMO5keCvhZ8wxjqHkeymlVyy02rRDM8nDHh6T/k432e0mn0JFH2GOJXgDb2ETEngH+3AIR9ADDt/gGn7Az+gquo1+R3/mo63obuc13EML/gL2eLV1</latexit>

split (V _k ) = min

v _i 2V k,v j 62V k d _{i, j}

<latexit sha1_base64="P1MXKjZmHPp7RZlf5r+khK1Oafk=">AAACrXichVHbahsxFNRub6l7c1qal76IhoJTgrPbh6ZQCkmTkD46UDsByxFaWWsr1mqFdNbELPtN+YN8RqHPfehvVF4b0jiFDgiGmTkcMScxSjqIop9BeO/+g4eP1h43njx99vxFc/1lz+WF5aLLc5Xbs4Q5oaQWXZCgxJmxgmWJEqfJ5GDun06FdTLX32FmxCBjIy1TyRl4iTav0hYx8vw9NVv4CyYZu6SlF6jBRGpMOp61jrcqXMf+FyJKpEBKn5Calj06Wfjz5Ko5pbI2fWgbT+kFJjqHpVDhIS3lNr7wQ1aOxkBuCG1uRu2oBr5L4iXZ3Nv/9eP6euOkQ5u/yTDnRSY0cMWc68eRgUHJLEiuRNUghROG8Qkbib6nmmXCDcq62Aq/88oQp7n1TwOu1b8nSpY5N8sSn8wYjN2qNxf/5fULSD8NSqlNAULzxaK0UBhyPL8SHkorOKiZJ4xb6f+K+ZhZxsHf8tYW4xQDcVk1fDPxag93Se9DO/7Yjk98RV/RAmvoDXqLWihGu2gPfUMd1EU8eB18Dg6Do3An7IYkPF9Ew2A58wrdQjj6A99q1Mw=</latexit>

f (p ^⇤ _p ) = max

p _p 2P p (G) f (p _p ) = max

p _p 2P p (G)

⇢

V min _k 2p ^p

⇢

v _i 2V min k ,v _j 62V k

d _{i, j}

<latexit sha1_base64="kn3fxFW0rDeK3RYORE9otqaDZvc=">AAACU3icbZDPahRBEMZ7x6hxNbrq0UthEDYSlhkP6iUY9CJ4ieBuAjubpqe3ZrezPT1Nd83iMszZh/LkM4gHj54EfQNFsPfPwSR+0PDxqyqq+susVp7i+GsrurJ19dr17Rvtm7d2bt/p3L038GXlJPZlqUt3kgmPWhnskyKNJ9ahKDKNx9ns1bJ+PEfnVWne0cLiqBATo3IlBQXEO/28m1p1+pjbPTiA1FcFr2cHSXNqIdWYU3fD5lxBqgwM+Gwf5vwMUlPSBjQw5rXah7MmdWoypb027+zGvXgluGySjdk9fPPnw4tfnz4f8c73dFzKqkBDUgvvh0lsaVQLR0pqbNpp5dEKORMTHAZrRIF+VK++38CjQMaQly48Q7Ci/07UovB+UWShsxA09RdrS/i/2rCi/PmoVsZWhEauF+WVBiphmSWMlUNJehGMkE6FW0FOhROSQuLntlivBeH7ZplMcjGHy2bwpJc87SVvQ0Qv2Vrb7AF7yLosYc/YIXvNjlifSfaRfWM/2M/Wl9bvKIq21q1RazNzn51TtPMXzC63/Q==</latexit>

f (p ^⇤ _p ) =

 p

k=1 Â

v _i 2V k ,v _j 62V k

d _{i, j}

!

§ Ad esempio, consideriamo il seguente grafo G e cerchiamo una partizione in p = 2 componenti connesse in modo da ottimizzare le due funzioni obiettivo «Minimo split» e «Somma delle distanze tra cluster»

V ₁ V ₂

V ₂ V ₁

Minimo split:

π ^* _p = {{1, 2}, {3, 4}}

f (π ^* _p ) = 30

Somma delle distanze tra cluster:

π ^* _p = {{1, 4}, {2, 3}}

f (π ^* _p ) = 220

Problemi di clustering

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 15

1 2

3 30 4

40

10

20 30 20

1 2

3 30 4

40

10

20 30 20

1 2

3 30 4

40

10

20 30 20

Altri problemi di partizionamento

Oltre all’equiparLzione e al clustering sono staL definiL molL altri problemi di parLzionamento di grafi:

§ Taglio della parLzione: dato G = (V, E) si assegna ad ogni spigolo un peso non negaLvo; il valore del taglio della parLzione π _p di G è la somma dei pesi degli spigoli «tagliaL», i cui estremi si trovano in due

componenL diverse

§ Il taglio può essere massimizzato o minimizzato, a seconda della specifica funzione obiePvo; nei seguenL casi i pasi sono non negaLvi e p = 2:

• Taglio non pesato : il peso assegnato agli spigoli è unitario; si vuole minimizzare il numero di spigoli «tagliaO»

• Taglio minimo : si vuole minimizzare il valore del taglio della biparOzione (si può risolvere con algoritmi di massimo flusso)

• Taglio massimo : si vuole massimizzare il valore del taglio della biparOzione (è NP-hard su grafi qualsiasi, polinomiale su specifiche classi di grafi)

§ ParLzionamento conLnuo

• agli spigoli del grafo è assegnata una «lunghezza» e la parOzione avviene oSmizzando una funzione calcolata in

base alla lunghezza degli spigoli di ciascuna componente: uno spigolo può essere tagliato in un punto qualsiasi,

contribuendo per parte della sua lunghezza ad una delle due componenO e per la restante all’altra

Complessità degli algoritmi per il partizionamento di grafi

I problemi di equipartizione e clustering sono generalmente NP-completi (o NP-hard) su grafi generici, ma possono essere risolti quasi sempre con algoritmi polinomiali su specifiche classi di grafi (tipicamente

cammini e alberi)

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 17

Equipartizione

Obiettivo Cammini Alberi

Norma L ₁ O(n p) NP-completo, O(n ² p) per caterpillar

Norma L ₂ O(n ² p) –

Norma L _∞ O(n p log ₂ p) –

Max-Min O(n p log ₂ p) O(n p log ₂ p)

Min-Max O(n p log ₂ p) O(n ² p ³ )

MUP O(n ³ ), O(n ² p log ₂ n) –

Clustering

Obiettivo Cammini Alberi

Inner dissimilarity O(n ² ) NP-completo

Maximum diameter O(n ² p) NP-completo

Minimo split O(n ² ) O(n ² )

Metodi generali per la soluzione di problemi di partizionamento

§ OPmizzazione su reL: si usano varianL degli algoritmi per problemi di massimo flusso (per problemi di clustering, con pesi/distanze/dissimilarità sugli spigoli)

§ Migrazione di gruppi: si genera una parLzione iniziale e poi si passa alla seguente «migrando» un gruppo di verLci da una componente ad un’altra, fino a quando mediante operazioni di «migrazione» non si

riesce più a migliorare la funzione obiePvo

§ Simulated annealing: simile alla tecnica precedente, salvo che per le condizioni di stop: l’algoritmo acceNa una «migrazione» di verLci anche se così facendo dovesse peggiorare il valore della funzione obiePvo; le condizioni che fanno terminare l’algoritmo sono basate su criteri locali

§ Semi: vengono selezionaL p verLci del grafo (semi) e vengono assegnaL alle p componenL della parLzione (es.: i verLci più distanL fra loro in un problema di clustering); poi vengono aggiunL alle componenL

anche gli altri verLci sulla base di criteri di similarità rispeNo ai verLci già presenL in ciascuna componente

§ Programmazione dinamica: si risolve il problema combinando la soluzione di soNoproblemi

§ ShiZing: si sposta l’aNenzione sui «tagli» assegnaL agli spigoli del grafo (Lpicamente un cammino o un albero per questo Lpo di algoritmi); i tagli sono assegnaL a priori a qualche spigolo, poi vengono spostaL su uno spigolo incidente con l’obiePvo di migliorare la funzione obiePvo

§ Programmazione lineare: si formalizza il problema con un sistema di equazioni e disequazioni lineari sulle

variabili i (verLci del grafo), j (indice delle componenL della parLzione), k (indice che idenLfica gli spigoli

del grafo)

Equipartizione di alberi con funzione obiettivo Max-Min

§ Vogliamo produrre una equipartizione di un albero T = (V, E) con |V| = n vertici e m = n – 1 spigoli, in p sottoalberi

(componenti connesse) indotti da una partizione dell’insieme dei vertici π _p = {V ₁ , ..., V _k }

§ Sui vertici dell’albero sono assegnati dei pesi non negativi w _i

§ Un taglio c è uno spigolo di (u, v) ∈ E(T) che viene rimosso per costruire la partizione di T; occorrono esattamente p – 1 tagli per produrre una p-partizione di T in componenti connesse

§ Imponiamo un orientamento naturale all’albero T per ottenere un albero con radice (scelta arbitrariamente fra i vertici di

grado 1); chiamiamo root component di π _p la componente che contiene la radice dell’albero

§ Una down component D _c di un taglio c è la componente

limitata dall’alto da c; indichiamo con W(D _c ) la somma dei pesi associati ai vertici della componente D _c

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 19

2

3 4

5

8 9 10

6 7

12

11

c ₁ c ₂

c ₃

w ₂

w ₃

w ₈

w ₄

w ₅ w ₆ w ₇

w ₉ w ₁₀ w ₁₁

w ₁₂

1 w ₁

Equipartizione di alberi con funzione obiettivo Max-Min

§ Il problema viene affrontato e risolto in tempo polinomiale da un algoritmo che utilizza la tecnica dello shifting dei tagli, inizialmente collocati sull’unico spigolo incidente la radice

§ Si vuole massimizzare il peso della

componente più leggera della partizione

§ Ad ogni passo si individua la componente di peso minimo W _min

§ Quindi si identifica il taglio su cui eseguendo lo shift si ottiene la down component più pesante

§ Se il peso della down component dopo l’esecuzione dello shift è comunque più pesante di W _min , si esegue lo shift e si reitera l’algoritmo, altrimenti si termina

Complessità:

dove con R(T) si è indicato il raggio di T:

<latexit sha1_base64="bI6Q36H91yFr94dH0whfiw9AwRo=">AAACFXicbVDLTgIxFO3gC/E16sKFmwZiMoRIZlioS6Ibd6LhlcBIOqVgQ+eRtmOcTPgLEz/ArX6CO+PWNV/gb9gZWAh4kpucnnNvbu9xAkaFNM2JlllZXVvfyG7mtrZ3dvf0/YOm8EOOSQP7zOdtBwnCqEcakkpG2gEnyHUYaTmjq8RvPRIuqO/VZRQQ20VDjw4oRlJJPf3oxjCCU6t4X4F3Rr1YSh9uMdfTC2bZTAGXiTUjhWq+W3qeVKNaT//p9n0cusSTmCEhOpYZSDtGXFLMyDjXDQUJEB6hIeko6iGXCDtODxjDE6X04cDnqjwJU/XvRIxcISLXUZ0ukg9i0UvE/7xOKAcXdky9IJTEw9NFg5BB6cMkDdinnGDJIkUQ5lT9FeIHxBGWKrO5LYFgSJKncZKMtZjDMmlWytZZ2bpVEV2CKbLgGOSBASxwDqrgGtRAA2AwBq/gDbxrL9qH9ql9TVsz2mzmEMxB+/4Fhfqevw==</latexit>

O((p 1) ² R(T ) + (p 1)m)

<latexit sha1_base64="Ix/+3gJqRTawLUrBJEWShFJvZyE=">AAACJXicbZDNSgMxFIUz/lv/Rl0KEixiC1JmXKgboejGZRVrC+0wZNK0RpPMkGTEYZhH8Dl8ALf6AoI7EVy5FHwKM60L23og8HHuvdybE0SMKu04H9bE5NT0zOzcfGFhcWl5xV5du1RhLDGp45CFshkgRRgVpK6pZqQZSYJ4wEgjuDnJ641bIhUNxYVOIuJx1BO0SzHSxvLtnfPSRRkeQU6Fn976NIMc3eV0ncFOyRi70HC54NtFp+L0BcfB/YVitdzeTHov3zXf/mp3QhxzIjRmSKmW60TaS5HUFDOSFdqxIhHCN6hHWgYF4kR5af9DGdw2Tgd2Q2me0LDv/p1IEVcq4YHp5EhfqdFabv5Xa8W6e+ilVESxJgIPFnVjBnUI83Rgh0qCNUsMICypuRXiKyQR1ibDoS2RYkiTuyxPxh3NYRwu9yrufsU9MxEdg4HmwAbYAiXgggNQBaegBuoAg3vwCJ7As/VgvVpv1vugdcL6nVkHQ7I+fwCbjaeR</latexit>

R(T ) = min _{v i} max _{v j} d(v _i , v _j )

c ₃

EquiparGzione di alberi con funzione obieHvo Max-Min

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 21

c ₁

c ₂ c ₃

2

3 4

5

8 9 10

6 7

12

11

10

20

4

2

8 10 5

8 2 20

4

1 5

W ₀ = 5 W ₁ = 0 W ₂ = 0 W ₃ = 93 p = 4

W _min = 0

W ₃ = 46 W ₂ = 47

c ₂

W ₁ = 10 W ₂ = 37 W _min = 5

c ₃

W ₁ = 30 W ₃ = 26

c ₂

W ₁ = 42 W ₂ = 25

c ₁

W ₀ = 27 W ₁ = 20

W _min = 20

c ₂

W ₂ = 20

W ₀ = 32

Equipartizione di cammini con funzione obiettivo L _∞

§ Un’immagine grafica «raster» è un mosaico di punL (pixel) più o meno fiP, a seconda della risoluzione dell’immagine

§ Ciascun pixel è caraNerizzato da un codice numerico che rappresenta il colore associato a quel pixel

§ Problema:

• si deve ridurre il numero di colori con cui è stata rappresentata un’immagine passando da n colori differenO a soli p < n colori disOnO

• come si scelgono i colori in modo da mantenere l’immagine ben comprensibile?

• Esempio su un caso reale:

o 5.500 × 3.700 = 20.350.000 pixel

o n = 300.000 colori immagine originale

o p = 256 colori immagine trasformata

§ Possiamo costruire un modello del problema trasformandolo nel problema di ottimizzazione combinatoria di partizionamento ottimo di un cammino

§ In particolare possiamo considerare un cammino P con n vertici; ogni vertice del cammino rappresenta uno dei colori dell’immagine, disposti secondo una scala che va dal colore più scuro (il nero) a quello più chiaro (il bianco)

• per semplicità consideriamo un’immagine in bianco e nero, dove invece dei colori abbiamo dei «toni di grigio»

§ Ad ogni vertice del cammino associamo un peso non negativo dato dal numero di pixel che nell’immagine hanno il colore associato al vertice del cammino

§ Vogliamo partizionare il cammino in p componenti / sotto-cammini di peso uniforme, in modo tale da assegnare nell’immagine rielaborata a tutti i pixel con un colore nella componente k lo stesso colore k, scelto dalla palette di soli p colori

120 55 70

60

EquiparGzione di cammini con funzione obieHvo L _∞

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 23

1 2 3 4 5 6 7 8 9 10

60 10 5 40 25 15 30 80 10 30

n = 10

p = 4

EquiparGzione di cammini con funzione obieHvo L _∞

§ Un grafo G = (V, E) è un cammino se V = {1, ..., n} ed E = {(i, i + 1), i = 1, ..., n – 1}

§ Ad ogni vertice è assegnato un peso w _i > 0

§ Sia p > 0 il numero di componenti connesse in cui intendiamo suddividere il cammino G «tagliando» p – 1 spigoli; risulta quindi:

• peso medio delle p componenti connesse:

• peso delle componenti connesse C ₁ , ..., C _p ⊂ V(G):

• funzione obiettivo « norma di Chebyshev » o norma L _∞ da minimizzare: f (π _p ) = max |W _k – µ|

§ Il numero di p-partizioni di un cammino con n vertici è dato da

per generare una p-partizione dobbiamo infatti scegliere p – 1 spigoli da rimuovere su un insieme di n – 1 spigoli complessivi (se n = 255 e p = 16 allora sono più di 629 × 10 ²¹ p -partizioni diverse)

<latexit sha1_base64="2URtlJ248fyQDAew8X/DF3Y0QEE=">AAACGHicbVDLSsNAFJ3UV62vqDvdDBbBVUlE1I1Q7MZlBfuAJoTJdNIOmUzCzEQtIeB3+AFu9RPciVt3foG/4bTNwrYeuHA4517uvcdPGJXKsr6N0tLyyupaeb2ysbm1vWPu7rVlnApMWjhmsej6SBJGOWkpqhjpJoKgyGek44eNsd+5J0LSmN+pUULcCA04DShGSkueedDxQngFHZlGXkahQzlseGEOHzzqmVWrZk0AF4ldkCoo0PTMH6cf4zQiXGGGpOzZVqLcDAlFMSN5xUklSRAO0YD0NOUoItLNJj/k8FgrfRjEQhdXcKL+nchQJOUo8nVnhNRQzntj8T+vl6rg0s0oT1JFOJ4uClIGVQzHgcA+FQQrNtIEYUH1rRAPkUBY6dhmtiSSIUUe84pOxp7PYZG0T2v2ec2+PavWr4uMyuAQHIETYIMLUAc3oAlaAIMn8AJewZvxbLwbH8bntLVkFDP7YAbG1y/V8Z+Z</latexit>

W _k = Â

i2C k

w _i

<latexit sha1_base64="OUsYbPkbnUixnZrr3hBwQRa2IFU=">AAACGnicbVC7TsMwFHXKq5RXgBEGQ4VUBqoEIWCsYGEsEn1IbVQ5rtNadRzLdhBVlIXv4ANY4RPYECsLX8Bv4LQZaOFIls89515d+/iCUaUd58sqLCwuLa8UV0tr6xubW/b2TlNFscSkgSMWybaPFGGUk4ammpG2kASFPiMtf3Sd+a17IhWN+J0eC+KFaMBpQDHSRurZ+91AIpxU+Il7fJAmFZHd0JTClD277FSdCeBf4uakDHLUe/Z3tx/hOCRcY4aU6riO0F6CpKaYkbTUjRURCI/QgHQM5Sgkyksmv0jhkVH6MIikOVzDifp7IkGhUuPQN50h0kM172Xif14n1sGll1AuYk04ni4KYgZ1BLNIYJ9KgjUbG4KwpOatEA+RiUWb4Ga2CMWQJg9pySTjzufwlzRPq+551b09K9eu8oyKYA8cggpwwQWogRtQBw2AwSN4Bi/g1Xqy3qx362PaWrDymV0wA+vzB7G1nsI=</latexit>

(n 1)!

( p 1)!(n p)!

<latexit sha1_base64="QgMxBsieewHwPqwYBwFzpoo3Tbs=">AAACH3icbZC7TsMwFIYdrqXcAowshgqJqUoYgKVSBQOMRaIXqSmR4zqtVduJbAeoQmaegxWJFR6BDbH2CXgN3MtAW37J0q//nKNz/AUxo0o7zsBaWFxaXlnNreXXNza3tu2d3ZqKEolJFUcsko0AKcKoIFVNNSONWBLEA0bqQe9yWK/fE6loJG51PyYtjjqChhQjbSLfPvB4AkvQCyXCqZulceaphPspLbnZnYAPPvXtglN0RoLzxp2YQvkKvnr+U6fi2z9eO8IJJ0JjhpRquk6sWymSmmJGsryXKBIj3EMd0jRWIE5UKx19JYNHJmnDMJLmCQ1H6d+JFHGl+jwwnRzprpqtDcP/as1Eh+etlIo40UTg8aIwYVBHcMgFtqkkWLO+MQhLam6FuIsMFW3oTW2JFUOaPGZ5Q8ad5TBvaidF97To3hhEF2CsHNgHh+AYuOAMlME1qIAqwOAZvIF38GG9WJ/Wl/U9bl2wJjN7YErW4BfCYKYq</latexit>

µ = 1 p

 n i=1

w _i

3 4

4

5 6

Equipartizione di cammini con funzione obiettivo L _∞

§ Per studiare l’algoritmo risolutivo è utile rappresentare graficamente le possibili p-partizioni del cammino P _n su una rete N composta mediante un grafo multipartito con p + 1 insiemi indipendenti

§ Esempio: n = 6, p = 4

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 25

1 2 3 4 5 6

C ₁ C ₂ C ₃ C ₄

numero di vertici dislocati nelle prime due componenti

0

1

2 3

2

3 1 2 3 4 5 6

1 2 3 4 5 6

s

t Ad ogni cammino da s a t su N

corrisponde una p-partizione di P _n

Equipartizione di cammini con funzione obiettivo L _∞

§ Per trovare la p-partizione π _p di P _n ottima per la funzione obiettivo Norma L _∞ procediamo assegnando i p – 1 tagli ai primi p – 1 spigoli del cammino, spostandoli poi verso destra uno alla volta fino a quando non sarà più possibile spostarli a destra, senza creare delle componenti vuote

§ In questo modo si passa da una partizione che corrisponde su N ad un certo cammino da s a t, ad un cammino «più basso» su N, partendo inizialmente dal cammino più in alto di tutti

§ Indichiamo con C _k la componente di scostamento massimo dalla media µ; l’algoritmo termina quando una di queste tre condizioni è verificata:

1. C _k è composta da un solo elemento e W(C _k ) – µ > 0

2. W(C _k ) – µ > 0 e k = 1 (la prima comp. di π p è la più pesante)

3. W(C _k ) – µ < 0 e k = p (l’ultima comp. di π p è la più leggera)

§ Se nessuna di queste condizioni è verificata l’algoritmo prosegue:

• allargando la componente C _k se W(C _k ) – µ < 0, spostando a destra il taglio che la limita a destra

• restringendo la componente C _k se W(C _k ) – µ > 0 , spostando a destra il taglio che la limita da sinistra

1

2

3

Equipartizione di cammini con funzione obiettivo L _∞

§ Esempio:

• consideriamo il cammino P ₆ = (V, E), con V = {1, 2, 3, 4, 5, 6}, E = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)} e pesi W = {w ₁ = 10, w ₂ = 13, w ₃ = 7, w ₄ = 10, w ₅ = 8, w ₆ = 4)

• supponiamo di voler ottenere una p-partizione con p = 4; risulta quindi µ = (10 + 13 + 7 + 10 + 8 + 4)/4 = 13

Università Roma Tre – Dipartimento di Matematica e Fisica

Marco Liverani, Ottimizzazione Combinatoria 27

3 4

4

5 6

10 13 7 10 8 4

C ₁ C ₂ C ₃ C ₄

0

1

2 3

2

3

10 13 7 10 8 4

10 13 7 10 8 4

s

t

– 3 0 – 6 9

10 13 7 10 8 4

– 1 4

– 3 0

– 1 – 3

– 3 7

– 1 – 3

10 6

π _p *

Equipartizione di cammini con funzione obiettivo L _∞

§ La complessità dell’algoritmo P ^ATH S ^HIFTING è O(n p log ₂ p) Dimostrazione:

• ognuno dei p – 1 tagli esegue al più n – 1 shift verso destra

• prima di eseguire uno shift occorre individuare la componente di scarto massimo dalla media

• utilizzando un heap binario per memorizzare gli scarti del peso delle p componenti dalla media µ, possiamo ridurre il tempo di ricerca della componente di scarto massimo a log ₂ p ∎

§ Identifichiamo una p-partizione di P _n con una sequenza (s ₀ , s ₁ , s ₂ , ..., s _{p – 1} , s _p ) , con s ₀ = 0 , s _p = n e s _k = i se e solo se il taglio k è sullo spigolo (i, i + 1)

§ Date due partizioni π’ _p e π’’ _p di P _n definite rispettivamente dai tagli (c’ ₁ , ..., c’ _{p – 1} ) e (c’’ ₁ , ..., c’’ _{p – 1} ) si dice che π’ _p è sopra a π’’ _p se s’ _k ≤ s’’ _k per ogni k = 0, ..., p

§ La proprietà «stare al di sopra» definisce un ordine parziale tra le p-partizioni π _p di P _n , per cui ∏ _p (P _n ) è

un reticolo

Equipartizione di cammini con funzione obiettivo L _∞

§ Lemma 1. Sia π ^t _p la parLzione finale trovata dall’algoritmo. TuNe le parLzioni π _p soNo π ^t _p sono tali che f (π _p ) ≥ f (π ^t _p )

Dimostrazione.

• Sia C _k ^t la componente di π ^t p che determina il valore di f (π ^t p ) (quella con il massimo scostamento dalla media).

Sia π p una generica parOzione soZo π ^t p

• Se C k = C k t allora ovviamente f (π _p ) ≥ f (π ^t _p )

• Sia C k ≠ C k t

o Se C k t = {v _i } , allora C k t è la più pesante e siccome vi deve appartenere a qualche componente di π p allora sicuramente risulta f (π _p ) ≥ f (π ^t _p )

o Sia k = 1, dunque C k t è la prima componente di π ^t p ed è quindi la più pesante: risulta W(C 1 t ) − μ ≥ 0 . Allora se π p è soZo π ^t p , C 1 t ⊂ C ₁ , quindi f (π p ) ≥ f (π ^t _p )

o Sia k = p, dunque C k t è l’ulOma componente di π ^t p ed è quindi la più leggera: W(C 1 t ) − μ ≤ 0 . Allora se π p è soZo π ^t p , C _p ⊂ C _p ^t , quindi anche in questo caso risulta f (π p ) ≥ f (π ^t _p ) ∎

Università Roma Tre – Dipar=mento di Matema=ca e Fisica

Marco Liverani, O>mizzazione Combinatoria 29

Equipartizione di cammini con funzione obiettivo L _∞

§ Lemma 2. Siano π ¹ _p , π ² _p , ..., π ^t _p le partizioni generate dall’algoritmo, sia π _p ^∗ una partizione ottimale. Se π _p ^∗ è sotto a π _p ^q , ma non è sotto π _p ^{q + 1} , allora π _p ^q è ottima.

Dimostrazione.

• Sia π p ∗ = {C ₁ ^∗ , ..., C _p ^∗ } la partizione ottimale che è al di sotto di π p q , ma non al di sotto di π p q + 1

• Tra π p q e π p q + 1 c’è solo un vertice di differenza in due componenti contigue, ossia i tagli delle due partizioni coincidono tranne uno, che è spostato a destra di un vertice

• Sia C k la componente di π p q di scarto massimo dalla media

o Se C k è la più pesante, allora il taglio s k che la limita a sinistra sarà s k + 1 in π p q + 1

o Se C k è la più leggera, allora il taglio s k + 1 che la limita a destra sarà s k + 1 in π p q + 1

• Quindi se π p ∗ non è al di sotto di π p q + 1 , ma è al di sotto di π p q , deve essere necessariamente π p q = π p ∗ ∎

Equipartizione di cammini con funzione obiettivo L _∞

§ Teorema. Almeno una delle parLzioni π ¹ _p , π ² _p , ..., π ^t _p generate dall’algoritmo è oPma.

Dimostrazione.

• π ¹ _p è al di sopra di ogni possibile p-parOzione del cammino

• Se una parOzione è al di sopra di π p ∗ allora tuZe le parOzioni generate prima di questa sono al di sopra di π p ∗ per transiOvità

• Sia m = max{r : π ^r p è sopra π p ∗ }. Dimostriamo che allora π ^m p è oSma. Per definizione di m c’è almeno una parOzione oSma soZo π ^m p

• Sia m = t. Allora f (π ^m p ) ≤ f (π _p ^∗ ) per il Lemma 1 e quindi π ^m p è oSma

• Sia m < t. Allora per la massimalità di m, π p ∗ non è soZo π p m + 1 e quindi per il Lemma 2, π ^m p è oSma ∎

Università Roma Tre – Dipar=mento di Matema=ca e Fisica

Marco Liverani, O>mizzazione Combinatoria 31

Riferimenti bibliografici

§ Marco Liverani, «Dispense del Corso di Ottimizzazione Combinatoria: Partizionamento ottimo di grafi in componenti connesse» (http://www.mat.uniroma3.it/users/liverani/doc/disp_oc_10.pdf)

§ Enzo L. Aparo, Bruno Simeone, Un algoritmo di equipartizione e il suo impiego in un problema di contrasto ottico, Estratto da Ricerca Operativa, N. 6, 1973, pp. 1-12

§ Claudio Arbib, A polynomial characterization of some graph partitioning problems, Information Processing Letters, 26, 1987/88, pp. 223-230

§ Ronald I. Becker, Yehoshua Perl, The shifting algorithm technique for the partitioning of trees, Discrete Applied Mathematics 62, 15-34, 1995

§ Marco Liverani, Aurora Morgana, Bruno Simeone, Gianni Storchi, Path equipartition in the Chebyshev norm, European Journal of Operational Research, 123, 2000, pp. 428-436

§ Mario Lucertini, Yehoshua Perl, Bruno Simeone, Most uniform path partitioning and its use in image processing, Discrete Applied Mathematics, 42, 1993, pp. 227-256

§ Yehoshua Perl, Stephen R. Shach, Max-min tree partitioning, Journal of the Association for Computing

Machinery, Vol. 28, No. 1, January 1981, pp. 5-15