Tugas teori graf

Exercise 3

The direct delivery problem is defined as follows : a transport company residing in city 0 has to carry out n transport orders V1 (i=1,...n). transport order V1 amounts to picking up cargo at place a1 and delivering this a place b1. not possible to combine order. after picking up order i it has to be delivered in b1 immediately.
the time needed for carrying out task V1 is equal to d(1) which accounts for travel time as well as time loading and unloading etcetera. the time for moving a truck from place j to place k is given by cjk. the tras porter ( who has only one transport  vehicle ) leaves place  0 at time zero. the goal to find a solution in which all order are carried out and the transport  returns back to place 0 as early as possible.
for the instance given below, compute an optimal schedule. is your strategy a general one in that it will solve every instance of the direct delevery problem optimally ?

Translate Indonesia :

Masalah pengiriman langsung didefinisikan sebagai berikut: sebuah perusahaan transportasi yang berada di kota 0 harus melaksanakan perintah n transportasi V1 (i = 1, ... n). Agar transportasi V1 berjumlah mengambil kargo di tempat a1 dan memberikan tempat ini b1. tidak mungkin untuk menggabungkan pesanan. setelah mengambil saya memesannya harus disampaikan dalam b1 segera.
waktu yang diperlukan untuk melaksanakan tugas V1 sama dengan d (1) yang menyumbang waktu perjalanan serta waktu bongkar muat dan sebagainya. waktu untuk memindahkan sebuah truk dari satu tempat ke tempat k j diberikan oleh Cjk. Tras penjaga pintu (yang hanya memiliki satu kendaraan transportasi) daun tempat 0 pada waktu nol. tujuan untuk mencari solusi yang memerintahkan semua dilakukan dan kembali transportasi kembali ke tempat 0 sedini mungkin.
untuk contoh diberikan di bawah ini, menghitung jadwal yang optimal. strategi Anda satu umum dalam bahwa hal itu akan memecahkan setiap contoh dari masalah delevery langsung secara optimal?

 Exercise 8

A group of 12 boys adn 12 girl decides to following ball room dancing classes. for each boy girls pair, it has been determined whatever or no they could be a dancing couple : see table bellow :

(a.) how many couples can be on the dance floor at the same time ?

(b.) assuming that your answer is less than 12, can you give a convincingargument that no perfect partition into 12 couples exist ?

Translate Indonesia :

Sekelompok 12 anak laki-laki dan 12 anak perempuan memutuskan untuk kelas menari bola ruangan berikut. untuk setiap pasangan anak laki-laki perempuan, telah ditetapkan apapun atau tidak ada mereka bisa menjadi pasangan menari: lihat tabel dibawah:

(A.) berapa banyak pasangan dapat berada di lantai dansa pada saat yang sama?(B.) asumsi bahwa jawaban Anda kurang dari 12, bisa Anda memberikan convincingargument bahwa tidak ada partisi yang sempurna menjadi 12 pasangan ada?

Exercise 9 

consider the network below. the number along the arcs give the value of the current flow, and the capacity of the arc, respectively. compute the maximum flow throught this network, and prove maximality by using a minimum capacity cut. decribe each step of your procedure.

translate to Indonesia:

mempertimbangkan jaringan di bawah ini. nomor sepanjang busur memberikan nilai arus, dan kapasitas busur masing-masing. menghitung aliran pemikiran maksimum jaringan ini, dan membuktikan maximality dengan menggunakan potongan kapasitas minimum. menggambarkan setiap langkah prosedur Anda.