Archive | Lý thuyết đồ thị RSS for this section

[LTDT]-Giải đề thi lần 1 – 10HCA2

Tác giả:

Trần Hán Huy – tranhanhuy.wordpress.com

Đề bài thi Lần 1 của 10HCA2

Link down: http://www.mediafire.com/?yhj9lr5qjtpl913
Xem đề trực tuyến: http://i275.photobucket.com/albums/jj319/darling0612/LTDT-DeThiLan1-10HCA2.jpg

Bài giải:

Link down: http://www.mediafire.com/?4zug3ibzggji4mu

May 19, 2011

[C++] Tìm chu trình Euler

Tác giả:

Trần Hán Huy – tranhanhuy.wordpress.com

Đề bài

Cho G=(X,E) là một đồ thị liên thông vô hướng gồm n đỉnh. Hãy tìm chu trình Euler

Lý thuyết

CHU TRÌNH Euler: dây chuyền đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần và đỉnh bắt đầu đi trùng với đỉnh kết thúc

Code chỉ giải quyết

Dùng tham số dòng lệnh với tập tin input
Đầu vào input : là ma trận kề

Do là ma trận kề nên ko thể hiện được cạnh song song và khuyên : mặt hạn chế
yêu cầu đưa vào là 1 đồ thị Euler

Chỉ giải quyết 1 đồ thị Euler
Đầu vào là file input, đầu xuất là màn hình
Sử dụng stack để giải quyết vấn đề
Chỉ xuất ra 1 chu trình Euler
vào ma trận kề nhưng được chuyển qua thành danh sách cạnh đầy đủ: tức 1 cạnh được lặp 2 lần. UV và VU

Code tìm chu trình Euler

void Euler::TimChuTrinh()
{
    //tao 1 stack
    vector<Canh> stack;
    //Cạnh tạm bằng cạnh đầu tiên trong dscanh
    Canh tam = m_DsCanh[0];
    //Xóa cạnh bắt đầu
    m_DsCanh.erase(m_DsCanh.begin() + 0);    
    //đưa cạnh đầu tiên vào stack
    stack.push_back(tam);
    //Kiểm tra số lượng stack
    while (stack.size()>0)
    {
        //lấy cạnh cuối cùng trong stack
        tam = stack[stack.size()-1];    
        //xóa cạnh giống với tam: tam là UV thì xóa đi VU
        for (int i = 0; i < (signed)m_DsCanh.size(); i++)
        {
            if (m_DsCanh[i].SoSanhDinh1(tam.getDinh2()) && m_DsCanh[i].SoSanhDinh2(tam.getDinh1()))
            //xoa cạnh VU
            m_DsCanh.erase(m_DsCanh.begin() + i);    
        }
         //cờ để đánh dấu có cạnh kề với đỉnh 2 của cạnh tạm ko?
        bool flag = false;
        //Tìm cạnh kề đầu tiên với đỉnh 2 của cạnh tạm
        for (int i = 0; i < (signed)m_DsCanh.size(); i++)
        {
            //tìm cạnh tiếp theo có đỉnh đầu là đỉnh 2 của cạnh tạm
            if (m_DsCanh[i].SoSanhDinh1(tam.getDinh2()))
            {
                //lấy cạnh i ra
                tam = m_DsCanh[i];
                //đưa vào stack
                stack.push_back(tam);
                //xóa cạnh i ra dsCanh
                m_DsCanh.erase(m_DsCanh.begin() + i);
                //bật cờ
                flag = true;
                //thoát ra vòng for
                break;
            }
        }
        //không có cạnh kề
        if (!flag)
        {
            //tiến hành lấy cạnh tạm nhưng đảo ngược đỉnh đầu cuối
            Canh t(tam.getDinh2(), tam.getDinh1());
            //đưa vào chu trinh euler
            m_ChuTrinh.push_back(t);
            //xóa cạnh tam ra khỏi stack
            stack.pop_back();//vì tam là cạnh cuối của stack nên chỉ popback đc rồi
        }
    }
}

Link source:

http://www.mediafire.com/?6l51wa8uka59gkf

May 17, 2011

[LTDT] – Chứng minh 6 định lý tương đương của cây

Trích lại:

Trần Hán Huy – tranhanhuy.wordpress.com

Link down:

http://www.mediafire.com/?e4dip787qwvl97u

Chứng minh 6 đinh lý tương đương về cây

Với đồ thị vô hướng G có n >= 2, có các tính chất tương đương sau:

G là một cây
G không có chu trình và có n-1 cạnh
G liên thông và có n-1 cạnh
G không có chu trình nhưng nếu thêm 1 cạnh nối hai đỉnh bất kỳ không kề nhau thì xuất hiện một chu trình
G liên thông nhưng nếu bớt đi một cạnh bất kỳ thì sẽ mất tính liên thông
Mỗi cặp đỉnh được nối với nhau bằng đúng một đường đi đơn

Gợi ý:

– Đồ thị không có chu trình khi và chỉ khi chu số của nó bằng 0 => c = m – n + p => m = n – p

(với: C – chu số, m – cạnh, n – đỉnh, p – số mảng liên thông)

Chứng minh:

– 1 => 2: vì G là cây thì G không có chu trinh và p = 1 mà m = n – p => m = n-1 cạnh

– 2 => 3: từ 2 cho điều này m = n – 1 => p = 1 => G chỉ có 1 mảng liên thông

– 3 => 4:

giả thiết có: m = n-1 và p=1. Với m=n-p và chu số = 0 => G không có chu trình.
Thêm 1 cạnh vào thì m tăng 1 còn n và p không đổi. Khi đó chu số C = m-n+p = 1 => đồ thị có 1 chu trình

– 4 => 5: c = 0 thì m = n – p

Giả sử G không liên thông, thế thì có ít nhất 2 đỉnh a, b không liên thông. Khi thêm cạnh a – b vào đồ thị vẫn không xuất hiện chu trình. (mâu thuẫn với 4) => đồ thị liên thông, p=1
Khi bớt đi 1 cạnh bất kỳ, đồ thị vẫn không có chu trình. Do đó m – 1 = n – p’. với p’ = 2 và đồ thị mất tính liên thông

– 5 => 6: G liên thông nên mỗi cặp đều có đường nối.

Giả sử cặp đỉnh a,b được nối bằng 2 đường khác nhau. Khi đó có cạnh E thuộc đường này nhưng không thuộc đượng kia. Ta bỏ cạnh E này đi, đồ thị vẫn liên thông. (mâu thuẫn với 5)

– 6 => 1: G liên thông