Bậc (lý thuyết đồ thị)
- Bài này viết về thuật ngữ "bậc" dùng trong lý thuyết đồ thị. Mời xem các bài bậc (toán học) hoặc bậc để đọc về các nghĩa khác.
Trong Lý thuyết đồ thị, bậc của một đỉnh v là số cạnh liên thuộc với v (trong đó, khuyên được tính hai lần). Bậc của v được ký hiệu là .
Trong một đồ thị có hướng, bậc trong của đỉnh v là số cung kết thúc tại v, còn bậc ngoài là số cung xuất phát từ v. Bậc trong và bậc ngoài của v được ký hiệu là và . Do đó, .
Đỉnh với được gọi là đỉnh cô lập. Đỉnh có được gọi là lá. Nếu mỗi đỉnh của đồ thị đều có bậc bằng nhau và bằng k thì đồ thị được gọi là đồ thị chính quy bậc k và đồ thị được coi là có bậc bằng k.
Đỉnh có được gọi là đỉnh phát, đỉnh có là đỉnh thu.
Một số định lý
Cho đồ thị G=(V,E),
Do mỗi cạnh liên thuộc với hai đỉnh nên số đỉnh bậc lẻ trong đồ thị là số chẵn.
Tham khảo
🔥 Top keywords: Đài Truyền hình Kỹ thuật số VTCTrang ChínhBảng xếp hạng bóng đá nam FIFAGiải vô địch bóng đá châu Âu 2024Đặc biệt:Tìm kiếmGiải vô địch bóng đá châu ÂuThích Minh TuệĐội tuyển bóng đá quốc gia RomâniaRomâniaĐội tuyển bóng đá quốc gia ÁoĐội tuyển bóng đá quốc gia SlovakiaSlovakiaĐội tuyển bóng đá quốc gia UkrainaĐội tuyển bóng đá quốc gia BỉGiải vô địch bóng đá châu Âu 2020Vòng loại giải vô địch bóng đá châu Âu 2024Đài Truyền hình Việt NamCleopatra VIIViệt NamRomelu LukakuKylian MbappéĐội tuyển bóng đá quốc gia PhápSloveniaGiải vô địch bóng đá thế giới 2022Bộ Chính trị Ban Chấp hành Trung ương Đảng Cộng sản Việt NamĐinh Tiến DũngGheorghe HagiCristiano RonaldoTô LâmBỉDanh sách phim điện ảnh Thám tử lừng danh ConanÁoGiải vô địch bóng đá châu Âu 2004Cửu Long Thành Trại: Vây thànhUkrainaThích Chân QuangKèo châu ÁĐặc biệt:Thay đổi gần đâyEuro