Parekatze (grafo teoria)

Grafo bateko parekatzea erpin edo puntu komunik ez duten ertzen multzo bat da, elkarren ondokoak ez diren ertzen multzo bat alegia.

Erpin bat parekatua dela esaten da parekatzearen ertz baten mutur batean badago. Bestela parekatu gabe dagoela esaten da.

Parekatze maximoa ahalik eta ertz kopuru handiena biltzen duen parekatzea da. Grafo batean parekatze maximo bat baino gehiago izan daiteke. Honako irudian parekatze maximo bana azaltzen da hiru grafotarako:

Parekatze maximala, bere barnean ez dagoen ertz bat gaineratzen bada, parekatze izaten jarraitzen ez duen parekatze hura da. Honako irudian parekatze maximal bana azaltzen da hiru grafotarako:

Parekatze osoa grafoko ertz guztiak hartzen dituena da.

Txandakazko ibilbidea parekatutako eta parekatu gabeko ertzak txandakatzen dituena da.

Ibilbide gehitzailea parekatu gabeko ertz batean hasi eta bukatzen den txandakazko ibilbidea da.

Elementu ezberdinak lotu edo parekatu behar direlarik, parekatzeen kopurua handiena izatea bilatzen denean erabiltzen dira parekatzearen alorreko kontzeptuak. Adibidez, langile ezberdinak lan ezberdinetara esleitu nahi ditugunean, burutu beharreko lan kopurua maximotu nahi denean erabil daiteke parekatzea. Esleipen bakoitzak kostu edo etekin ezberdinak dituenean, esleipen ebazkizuna sortzen da.

Kanpo estekak

• Datuak: Q1065144
• Multimedia: Matching (graph theory) / Q1065144