Thành viên:Wild Lion/Nháp

Bài 1: Trực quan hóa đồ thị

Trực quan hóa đồ thị (tiếng Anh: graph drawing) là một nhánh của lý thuyết đồ thị, áp dụng topo và hình học để vẽ nên hình ảnh 2 chiều của đồ thị.

Rất nhiều đối tượng được mô hình hóa bằng đồ thị, ví dụ: mạng lưới giao thông, mạng lưới internet, ... . Việc biểu thị các đối tượng này dưới dạng hình ảnh đồ thị đem lại nhiều tiện lợi khi nghiên cứu các thuộc tính của chúng.

Trực quan hóa đồ thị có nhiều ứng dụng trong mạng xã hội, công nghệ sinh học (mô tả các phân tử sinh học), mạng máy tính, thiết kế mạch điện tử, vẽ bản đồ, ... .

Các ứng dụng

• Sự biểu hiện các quan hệ xã hội thành sơ đồ (tiếng Anh: sociogram) có nhiều ứng dụng trong mạng xã hội (tiếng Anh: social network).
• Biểu đồ Hasse biểu diễn quan hệ thứ tự riêng phần bằng vẽ đồ thị.

Một số chương trình vẽ đồ thị

• Graphviz, chương trình mã nguồn mở vẽ đồ thị do AT&T điều hành.
• yEd, chương trình vẽ đồ thị rất phổ biến với chức năng layout.
• Routing, chương trình vẽ đồ thị với các bước giống như thiết kế mạch điện tử
• International Symposium on Graph Drawing
• Microsoft Automatic Graph Layout, thư viện .NET cho việc vẽ đồ thị.
• Tulip (software)
• Hypercube (software), một công cụ mô phỏng đồ thị mã nguồn mở.

Bài 4:Định lý Cauchy (lý thuyết nhóm)

Định lý Cauchy: phát biểu rằng:

Cho nhóm G hữu hạn. Nếu cấp của G chia hết cho p, và p là số nguyên tố, thì tồn tại ít nhất một phần tử a thuộc G có cấp bằng p.

Chứng minh

Chứng minh dựa vào quy nạp theo n=|G|.Xét 2 trường hợp, G là nhóm Abel và G không phải là nhóm Abel.

Trường hợp 1: G là nhóm Abel.

Nếu |G| là số nguyên tố thì suy ra luôn điều phải chứng minh. Nếu |G| là hợp số, như vậy tồn tại nhóm con chuẩn tắc không tầm thường H của |G|. Nếu |H| chia hết cho p thì theo giả thiết quy nạp, suy ra luôn trong H có phần tử bậc p. Trái lại, nếu |H| không tầm

Bài 5: Hình cầu

Cho một khối cầu có bán kính R, công thức tính thể tích của chỏm cầu có bán kính đáy là r là:

$V=\pi \cdot \left({\frac {2R^{3}}{3}}-{\frac {2R^{2}+r^{2}}{3}}{\sqrt[{}]{R^{2}-r^{2}}}\right)$,

nếu lấy h là chiều cao của chỏm cầu ($h=R-{\sqrt {R^{2}-r^{2}}}$) thì ta sẽ thu được công thức ngắn gọn hơn:

$V={\frac {\pi h^{2}\left(3R-h\right)}{3}}$.

Bài 7: Năng lượng của đồ thị

Trong Lý thuyết đồ thị, khái niệm năng lượng đồ thị (tiếng Anh: energy graph) được định nghĩa như sau. Cho đơn đồ thị G với n đỉnh. Gọi A là ma trận kề của G. Khi đó năng lượng đồ thị là đại lượng:

$E(G)=\sum _{i=1}^{n}|\lambda _{i}|$

trong đó, $\lambda _{i}$, $i=1,\ldots ,n$ là các giá trị riêng của ma trận liền kề A.

Tính chất

Giới hạn của năng lượng đồ thị

Nếu M là chỉ số thỏa mãn $|\lambda _{M}|=max_{i=1,2,...,n}|\lambda _{i}|$ thì $E(G)\geq 2\cdot |\lambda _{M}|$.

Chứng minh

Thật vậy, tổng các giá trị của $\lambda _{i}$ sẽ bằng vết của ma trận A. Mặt khác, G là đồ thị đơn, do đó tất cả phần tử trên đường chéo của ma trận kề A đều bằng 0, do đó:

$\sum _{i=1}^{n}\lambda _{i}=0$.

Suy ra:

$\lambda _{M}=-\sum _{i=1,i\not =M}^{n}\lambda _{i}$,

suy ra:

$E(G)=\sum _{i=1}^{n}|\lambda _{i}|\geq |\lambda _{M}|+|\sum _{i=1,i\not =M}^{n}\lambda _{i}|=2\cdot |\lambda _{M}|.\Box$

Chú thích

• 1. D. M. Cvetkovi´c, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, New York, 1979.
• 2. I. Gutman, The energy of a graph, Ber. Math. Stat. Sekt. Forschungszentrum Graz., 103: 1–22 (1978).
• 3. I. Gutman, The energy of a graph: old and new results, Algebraic Combinatorics and Applications, 196–211, Springer-Verlag, Berlin, 2001.